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

Có ~q~ truy vấn, mỗi truy vấn có dạng ~l_i,r_i~ ~(l_i < r_i)~, hãy in ra tổng của số lớn nhất và số lớn thứ hai trong đoạn ~[l_i,r_i]~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số phần tử của dãy.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• Dòng thứ ba gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~l_i,r_i~ miêu tả truy vấn.

Constraints

• ~2 \le n \le 3*10^5~
• ~1 \le a_i \le 10^9~

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~n \le 2000~
• Subtask ~2~ (~50\%~ số điểm): ~n \le 3*10^{5}~

Output

• Với mỗi truy vấn, in ra kết quả cần tính.

Sample Input 1

5
1 4 2 3 5
3
1 2
1 5
3 5

Sample Output 1

5
9
8

Bạn được cho một dãy số nguyên ~a~ gồm ~n~ phần tử ~a_0,a_2,...,a_{n-1}~.

Mỗi bước, dãy ~a~ sẽ thay đổi thành một dãy độ dài ~n~ khác - coi là dãy ~b~, với phần tử ~b_i = gcd(a_i,a_{(i+1)\%n})~.

Giả sử nếu ~a = [16,24,10,5]~, sau một bước sẽ thành ~ b=[gcd(16,24), gcd(24,10), gcd(10,5), gcd(5,16)]=[8,2,5,1]~. Như vậy, sau một bước, dãy ~a = [16,24,10,5]~ sẽ trở thành ~a = [8,2,5,1]~.

Hãy tìm số bước ít nhất sao cho dãy ~a~ bằng nhau.

Input

• Dòng đầu vào đầu tiên chứa số nguyên ~n~.

• Dòng tiếp theo có ~n~ số nguyên ~a_0, a_1, ..., a_{n-1} ~.

Constraints

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

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 2000~.
• Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Output

• Gồm một số nguyên duy nhất là số bước để dãy ~a~ bằng nhau.

Sample Input 1:

4
16 24 10 5

Sample Output 1:

3

Sample Input 2:

4
42 42 42 42

Sample Output 2:

0

Cho một cây ~n~ nút và ta định nghĩa nút ~1~ là gốc của cây.

Bây giờ ta có ~q~ truy vấn, mỗi truy vấn có dạng: ~l_i,r_i~ ~(1 \le l_i \le r_i \le n)~.

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ ~l_i~ đến ~r_i~.

Input

• Dòng đầu vào đầu tiên chứa số nguyên ~n~ - thể hiện số nút của cây.

• ~n-1~ dòng tiếp theo: mỗi dòng gồm ~2~ số nguyên ~x,y~ - thể hiện cạnh nối giữa hai đỉnh ~x~ và ~y~.

• Dòng tiếp theo, chứa số ~q~ thể hiện số lượng truy vấn.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i,r_i~ ~(1 \le l_i \le r_i\le n)~.

Constraints

• ~1 \le n \le 3*10^5~.

Subtask

• Subtask ~1~ ~(50\%)~: ~n \le 2000~.
• Subtask ~2~ ~(50\%)~: Không có điều kiện gì thêm.

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Sample Input 1:

5
1 4
2 5
3 5
2 4
2
2 4
1 3

Sample Output 1:

4
1

Trong dịp lễ giáng sinh, siêu thị ~ABC~ có chính sách giảm giá ~n~ mặt hàng. Các mặt hàng được trưng bày theo thứ tự từ trái qua phải với mức giá ưu đãi là ~p_i~, với số lượng không giới hạn với mỗi loại mặt hàng. Có ~m~ khách hàng thân thiết vô cùng yêu thích chương trình giảm giá này, người thứ ~i~ mang tới số tiền là ~t_i~ và sẽ đi từ vị trí ~l_i~ tới vị trí ~r_i~. Tại mỗi vị trí, người này sẽ cố gắng mua nhiều nhất số hàng có thể tới khi không còn đủ tiền mua.

Yêu cầu: Hãy xác định số tiền còn lại của từng người sau khi mua hàng.

Input

• Dòng đầu tiên chứa số nguyên dương ~n, m~
• Dòng thứ hai chứa ~n~ số, số thứ ~i~ là ~p_i~ mô tả giá tiền của mặt hàng thứ ~i~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~t_i,l_i,r_i~ xác định số tiền và khoảng cách di chuyển của người thứ ~i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le p_i,t_i \le 10^{18}~

Subtask

• Subtask ~1~ ~(50\%)~: ~1 \le n,m \le 5000; 1 \le p_i, t_i \le 10^9~
• Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm

Sample Input 1

5 3
5 3 2 4 6
8 5 5
107 1 4
7 3 5

Sample Output 1

2
0
1

Một dãy số ~(b_1, b_2, ..., b_m)~ được gọi là có thể tối giản nếu tồn tại một phần tử *~x~ thỏa mãn:*

• ~x~ là duy nhất trong dãy.

• Mọi phần tử ~b_1, b_2, ..., b_m~ đều chia hết cho ~x~.

Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản. ~(1 \le l < r \le n)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ .

Constraints

• ~1 \le n \le 3 * 10^5~.
• ~1 \le a_i \le 10^9~.

Subtask

• Subtask ~1~ ~(50\%)~: ~1 \le n \le 1000~
• Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm

Output

• Gồm một dòng duy nhất là số dãy tìm được.

Sample Input 1

5
4 3 6 4 2

Sample Output 1

3

Notes

• Các đoạn thỏa mãn là ~[2, 3], [4, 5], [3, 5]~.

Cho dãy ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~, ~r~. Với mỗi truy vấn bạn cần đếm xem, có bao nhiêu cách chia dãy ~a_l, a_{l+1}, \dots, a_r~ thành hai phần khác rỗng sao cho mỗi phần gồm các phần tử đứng liên tiếp và đôi một phân biệt.

Input

Dòng đầu chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 5 \times 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).

~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~, ~r_i~ (~1 \le l_i \le r_i \le n~) mô tả truy vấn thứ ~i~.

Output

In ra ~q~ dòng, dòng thứ ~i~ gồm một số nguyên là kết quả cho truy vấn thứ ~i~.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, q \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i \le 10~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

5 3
1 3 1 2 2
1 5
1 2
3 5

Output 1

0
1
1

Input 2

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

Output 2

1
3
3
0