Cho dãy số nguyên \(a_1,a_2,…,a_n)\). Cho Q truy vấn, mỗi truy vấn có dạng \(l,r.\)

Yêu cầu: Với mỗi truy vấn \(l r\), Hãy tìm giá trị\( min⁡(a_l,a_(l+1),…,a_r ).\)

Input

• Dòng đầu tiên chứa số nguyên \(n,q (2≤n≤2*10^5 ).\)

• Dòng thứ hai chứa \(n\) số nguyên\( a_1,a_2,…,a_n (a_i≤10^9 ).\)

• \(q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(l,r(1≤l≤r≤n).\)

Output

• Ghi ra \(q\) dòng, mỗi dòng là kết quả của test tương ứng.

Sample Input

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

Sample Output

2
1
1
4