Dãy số kì diệu và truy vấn tối thiểu

Nhà toán học Alice phát hiện ra một dãy số thần bí gồm \(n\) phần tử và muốn tìm hiểu về các giá trị nhỏ nhất trong những đoạn con của dãy số đó. Dãy số này, \(a_1, a_2, \dots, a_n\), được Alice gọi là "Dãy số kì diệu". Cô cho rằng mỗi đoạn con của dãy đều mang một thông tin bí ẩn về một thế giới song song mà cô muốn khám phá. Để giải mã dãy số này, Alice cần sự trợ giúp của bạn để tìm ra giá trị nhỏ nhất trong một số đoạn con nhất định.

Để tăng tính thách thức, Alice không thể tìm trực tiếp mà phải dựa vào các truy vấn mà bạn có thể xử lý cho cô ấy. Đây là một công việc khó khăn, nhưng với tài năng lập trình của bạn, Alice tin rằng bạn có thể giúp cô ấy khám phá tất cả những đoạn con mong muốn.

Nhiệm vụ:

Cho một dãy số \(a_1, a_2, \dots, a_n\) và \(m\) truy vấn, mỗi truy vấn yêu cầu tìm phần tử nhỏ nhất trên đoạn \(a_{l}, a_{l+1}, \dots, a_{r}\). Bạn cần xử lý mỗi truy vấn để trả về giá trị nhỏ nhất cho Alice. Hãy giúp Alice để cô ấy có thể tiếp tục khám phá những điều bí ẩn của dãy số này.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) \((n, m \leq 10^5)\), lần lượt là độ dài của dãy số và số lượng truy vấn Alice cần thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((-10^9 \leq a_i \leq 10^9)\), là các phần tử trong dãy số.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i \leq r_i \leq n)\), mô tả một truy vấn. Truy vấn yêu cầu bạn trả về phần tử nhỏ nhất trên đoạn \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\).

Output

• Với mỗi truy vấn, in ra một số nguyên tương ứng là kết quả của truy vấn đó, mỗi kết quả trên một dòng.

Example

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

2
3
7

Scoring

• \(30\%\) số test có \(n, m \leq 5000\).

• \(30\%\) số test có \(r - l + 1 = 2^k\), với \(k \geq 0\).

• \(40\%\) số test còn lại không có ràng buộc gì thêm.