时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定一个长度为 \(n\) 的整数数组 \(A[1]、A[2]、…、A[N](-10^9≤A[i]≤10^9)\)。

　　然后给出 \(m\) 个查询操作，每次查询 \(A[i]..A[j]\) 的最小元素。

【输入格式】

　　第一行包含两个整数 \(n\) 和 \(m\)，表示数组有 \(n\) 个元素，\(m\) 表示有 \(m\) 个查询操作；
　　接下来的 \(n\) 行，每行一个整数，第 \(i+1\) 行的整数表示 \(A[i]\)；
　　再接下来的 \(m\) 行，每行两个整数 \(i,j（i≤j）\)，表示一个查询操作。

【输出格式】

　　共有 \(m\) 行，每行一个整数，第 \(i\) 行的整数表示对应查询的结果。

【输入输出样例】

　Input

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

　Output

4
3
3
2
3

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤100000\)，\(1≤M≤180000\)。

【来源】

　　Mr.he