Mức Thấp Nhất

Cho một dãy số nguyên $a_1,a_2,\dots ,a_n$ không thay đổi trong suốt quá trình xử lý. Mỗi truy vấn xác định một đoạn chỉ số đóng $[l,r]$. Với từng truy vấn, hãy tìm giá trị nhỏ nhất xuất hiện trong đoạn $a_l,a_{l+1},\dots ,a_r$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$ - số phần tử của dãy và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Mỗi dòng trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$, mô tả một truy vấn.

Output

• Với mỗi truy vấn, in giá trị nhỏ nhất trên đoạn $[l,r]$ ở một dòng riêng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i\le 10^9$ với mọi $1\le i\le n$.
• $1\le l\le r\le n$ trong mọi truy vấn.
• Mỗi truy vấn được thực hiện trên dãy ban đầu; không có thao tác cập nhật.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

3
2
2
2