An có một dãy số gồm \(N\) phần tử được đánh số từ \(1\) đến \(N\). An cần trả lời \(Q\) câu hỏi, mỗi câu hỏi yêu cầu tìm giá trị nhỏ nhất trong đoạn từ \(l\) đến \(r\).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng 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, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra giá trị nhỏ nhất tìm được trên một dòng.

Ví dụ

Input:

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

Output:

1
1
3