Một dãy các số ~a_1,a_2,...,a_n~ được gọi là dãy kẹp nếu ~a_1 \le a_i \le a_n~, ~\forall i \in [1,n]~. Nếu ~n \le 2~ thì là dãy kẹp nếu ~a_1 \le a_n~.

Các ví dụ về dãy kẹp: ~[1],[1,1],[3,4,3,4],[1,3,2,4]~. Các ví dụ về dãy không phải dãy kẹp: ~[],[2,3,1],[2,1,4,3]~.

Cho mảng ~a = [a_1,a_2,...,a_n]~, hãy đếm xem có bao nhiêu mảng con liên tiếp của ~a~ là dãy kẹp.

Input

• Dòng đầu chứa số nguyên dương ~𝑛~ ~(𝑛 ≤ 10^6)~.
• Dòng sau chứa dãy ~a~ ~(1 \le a_i \le 10^9)~.

Subtask

• Subtask ~1~ ~(10\%)~ : ~n \le 300~
• Subtask ~2~ ~(20\%)~ : ~1 \le n \le 10^5, 1 \le a_i \le 2~
• Subtask ~3~ ~(20\%)~ : ~n \le 5000~
• Subtask ~4~ ~(30\%)~ : ~n \le 10^5~
• Subtask ~5~ ~(20\%)~: Không giới hạn gì thêm

Output

• In ra một số là kết quả bài toán.

Sample Input 1

5
1 2 4 3 5

Sample Output 1

11

Sample Input 1

8
2 1 6 3 6 7 8 5

Sample Output 1

18

Cho một dãy ~A~ gồm ~n~ phần tử nguyên dương ~A_1, A_2, ..., A_n~.

Một dãy ~B~ được gọi là tương thích với dãy ~A~ khi và chỉ khi:

• ~B~ gồm ~n + 1~ phần tử nguyên dương.
• Với mọi ~1 \le i \le n~, ta có ~LCM(B_i, B_{i + 1}) = A_i~.

Ví dụ với dãy ~A= [2, 6]~ thì dãy ~B~ thoả mãn là ~B = [1, 2, 3]~.

Nhiệm vụ của bạn là đếm số dãy ~B~ thoả mãn với dãy ~A~ cho trước. Vì kết quả có thể rất lớn nên hãy in ra sau khi lấy ~mod~ với ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số số nguyên dương ~n~ ~(1 \le N \le 10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^6)~.

Output

• In ra số dãy ~B~ thoả mãn sau khi mod cho ~10^9 + 7~.

Scoring

• Có ~20\%~ số test có ~n \le 200~ và ~A_i \le 2000~.
• Có ~20\%~ số test có ~A_i = 2^k~ với ~k~ là một số nguyên không âm.
• Có ~30\%~ số test có ~A_i \le 5000~.
• Có ~30\%~ số test không có giới hạn gì thêm.

Sample Input 1

2
2 6

Sample Output 1

5

Sample Input 2

6
3 3 3 3 3 3

Sample Output 2

34

Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~.

Một "Tập Phủ Đỉnh" (Vertex Cover) là một tập đỉnh ~S~ sao cho với mọi cạnh ~(u, v) \in E~, ta luôn có ~u~ hoặc ~v~ thuộc ~S~. Gọi ~V(S)~ là giá trị của tập phủ đỉnh này, ~V(S)~ = chênh lệch nhỏ nhất giữa các index đỉnh của tập ~S~. Nói cách khác, nếu ~S~ bao gồm các đỉnh ~u_1, u_2, ..., u_k~, thì ~V(S) = min(|u_i - u_j|) (i \neq j)~.

Nhiệm vụ của bạn là tìm ra một tập phủ đỉnh sao cho ~V(S)~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 2 \times 10^5)~

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i, v_i~ miêu tả cạnh thứ ~i~.

Output

• In ra giá trị ~V(S)~ tìm được.

Sample Input 1

7 6

1 2
1 6
5 7
1 4
2 3
1 3

Sample Output 1

2

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử.

Bạn có thể thực hiện thao tác sau vô số lần:

• Chọn ra một đoạn ~[l,r]~ ~(1 \le l \le r \le n)~ và thay thế ~a_l = a_{l+1} = ... = a_r = \frac{a_l+a_{l+1}+...+a_r}{r-l+1}~. Ví dụ, nếu có dãy ~a = [1,3,6,7]~ và bạn chọn đoạn ~[2,3]~, ta sẽ thu được dãy ~a = [1,4.5,4.5,7]~.

Hãy in ra dãy ~a~ có thứ tự từ điển nhỏ nhất mà bạn có thể thu về được.

Dãy ~a~ có thứ tự từ điển bé hơn dãy ~b~ có cùng độ dài khi: gọi vị trí ~i~ là vị trí đầu tiên mà ~a~ và ~b~ khác nhau, ta có ~a_i < b_i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị ~a_i~ của dãy ~a~ tốt nhất tìm được. Kết quả lấy ~9~ chữ số sau dấu phẩy.

Constraints .

• ~1 \le n \le 2\times10^5~
• ~1 \le a_i \le 10^6~

Subtask

• Sub ~1~ (~30\%~): ~n \le 20~.
• Sub ~2~ (~30\%~): ~n \le 2000~.
• Sub ~3~ (~40\%~): ~n \le 2\times10^5~.

  Sample Input 1

5
1 3 2 2 3

Sample Output 1

1.000000000
2.333333333
2.333333333
2.333333333
3.000000000

Explanation 1

Thực hiện ~1~ thao tác trên đoạn ~[2,3]~.

Cho ~S~ là một tập các từ (word). Từ tập ~S~, ta có thể tạo ra các chuỗi (string) bằng cách viết liền các từ của ~S~ (mỗi từ có thể sử dụng nhiều lần). Giả sử ~A~ là một chuỗi tạo ra bằng cách trên:

~A = x_{1} x_{2} \ldots x_{k}~ với ~x_{i} \in S, \forall i \in \{1, 2, \ldots, k\}~

Khi đó ~X = x_{1}, x_{2}, \ldots, x_{k}~ được gọi là một dẫn xuất của chuỗi ~A~. Rõ ràng là một chuỗi có thể có nhiều dẫn xuất, ví dụ:

~S = \{ab, ba, a\}, A = aba = ab + a = a + ba~

Tập ~S~ được gọi là một bộ mã nếu không tồn tại chuỗi nào có nhiều hơn một dẫn xuất. Khi đó, mọi dãy các số tự nhiên nhỏ hơn |S| đều có thể mã hóa thành một chuỗi mà chỉ có một cách giải mã. Bài toán kiểm định mã là kiểm tra xem ~S~ có phải là một bộ mã hay không. Yêu cầu: Kiểm tra xem ~S~ có phải là một bộ mã hay không. Trong trường hợp ~S~ không phải là một bộ mã, hãy tìm chuỗi ngắn nhất có nhiều hơn một dẫn xuất.

Input

• Dòng đầu tiên chứa ~n~ là lực lượng tập ~S~.
• ~n~ dòng tiếp theo, mỗi dòng chứa một từ của ~S~. Các từ chỉ chứa các chữ cái latin thường. Tổng độ dài các từ không quá ~2000~ và không có hai từ nào giống nhau.

Output

• Nếu ~S~ là một bộ mã, in ra ~-1~.
• Ngược lại, in ra chuỗi ngắn nhất có nhiều hơn một dẫn xuất. Trong trường hợp có nhiều chuỗi ngắn nhất, in ra chuỗi có thứ tự từ điển nhỏ nhất.

Scoring

• Subtask ~1~ (~30\%~ số điểm): Các từ chỉ gồm các ký tự a, b, c và có không quá ~10~ từ trong tập ~S~; kết quả hoặc là ~-1~ hoặc là một chuỗi có độ dài không quá ~10~.
• Subtask ~2~ (~30\%~ số điểm): tổng độ dài các từ không quá ~500~; kết quả hoặc là ~-1~ hoặc là một chuỗi có độ dài không quá ~500~.
• Subtask ~3~ (~40\%~ số điểm): không có ràng buộc gì thêm.

Sample Input 1

3
ab
ba
a

Sample Output 1

aba

Sample Input 2

2
a
b

Sample Output 2

-1