Cho dãy số \(a_{1}, a_{2}, \ldots, a_{n}\) và \(m\) truy vấn \(l, r\). Với mỗi truy vấn đưa ra phần tử bé nhất trong đoạn \(a_{l}, a_{l + 1}, \ldots, a_{r}\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n, m\) \((n, m \leq 10^{5})\).
• Dòng thứ \(2\) chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) ghi \(2\) số nguyên \(l_{i}, r_{i}\) là xác định truy vấn thứ \(i\) \((1 \leq l_{i} \leq r_{i} \leq n)\).

Output

• \(m\) dòng, mỗi dòng một số nguyên tương ứng với kết quả truy vấn thứ \(i\).

Example

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

2
3
7