RMQ - Range Minimum Query

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: phần tử nhỏ nhất trong đoạn \([a, b]\) là gì?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(q\): số phần tử và số truy vấn
• Dòng thứ hai là \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các phần tử của mảng
• \(q\) dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên \(a\) và \(b\): phần tử nhỏ nhất trong đoạn \([a, b]\) là gì?

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra đáp án của mỗi truy vấn

Example

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

2
1
1
4

Ước số chung lớn nhất của dãy số nguyên dương \(A\) không rỗng là số nguyên dương \(d\) lớn nhất
đồng thời là ước của mọi số trong dãy \(A\).

Cho mảng số nguyên dương \(a_1, a_2, . . ., a_n\) và số nguyên \(k\).

Hãy tìm đoạn \(a_i, a_{i+1}, . . ., a_{i+k-1}\) có ước số chung lớn nhất và đưa ra ước số chung đó.

Input

• Dòng đầu tiên chứa số nguyên \(n\) và \(k\) (\(2 \le n \le 5 \times 10^5, 2 \le k \le n\)),
• Dòng thứ 2 chứa \(n\) số nguyên \(a_1, a_2, . . ., a_n\) (\(1 \le a_i \le 10^{18}, i = 1 ÷ n\)).

Output

• Đưa ra một số nguyên – ước số chung lớn nhất tìm được.

Example

10 4
2 3 4 8 12 6 12 18 4 3

6

Đại gia phố núi BK đã xin phép được khai thác một khu rừng trồng lấy gỗ làm nhà sàn. Khu rừng của anh có tất cả \(n\) cây. Cây thứ \(i\) có chiều cao là \(a[i]\). Để thuận lợi cho việc chặt lấy gỗ, anh cần chọn ra một số cây liên tiếp bắt đầu từ vị trí \(l\) đến \(r\) (\(1 ≤ l ≤ r ≤ n\)) thỏa mãn điều kiện sau:

• Tồn tại 1 vị trí \(j\) (\(l ≤ j ≤ r\)) sao cho với mọi cây \(i\) (\(l ≤ i ≤ r\)) thì \(a[i]\) đều chia hết cho \(a[j]\).
• Tìm ra các cặp \(l,r\) thỏa mãn điều kiện trên sao cho \(r-l\) lớn nhất.

Yêu cầu:

• Cho 1 dãy \(a\) gồm \(n\) số nguyên dương. Hãy tìm giá trị \(r - l\) thỏa mãn điều kiện và in ra các giá trị \(l\) của những cặp số đó.

Input:

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số gồm các số nguyên dương có giá trị nhỏ hơn \(10^6\).

Output:

• Dòng đầu tiên in ra số \(k\) là số các cặp (\(l,r\)) thỏa mãn điều kiện và giá trị \(r-l\) lớn nhất cách nhau bởi 1 dấu cách .
• Dòng thứ hai in ra \(k\) số là các giá trị \(l\) của các cặp số được sắp xếp từ nhỏ đến lớn.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n ≤ 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n ≤ 5\times 10^5\).

5
4 6 9 3 6

1 3
2

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một đoạn con liên tiếp với độ dài giữa \(a\) và \(b\).

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(a\) và \(b\): kích thước của mảng và độ dài tối thiểu và tối đa của đoạn con.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị mảng.

Output

• In một số nguyên: tổng đoạn con lớn nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a \le b \le n\)
• \(-10^9 \le x_i \le 10^9\)

Example

8 1 2
-1 3 -2 5 3 -5 2 2

8