问题描述

洞窟里有一道长长的通道，它由$N(1≤N≤25000)$ 段道尾相连构成，编号分别为$1$到 $N$。每个通道有一个阈值，其范围在 $[1，10^9]$，如果奶牛要依次通过 i..j 的通道，那奶牛的体重指数就不能超过 i..j 通道中阈值的最小值。贝茜有 $Q(1≤Q≤25000)$个问题，想请教你由 i 到 j 的通道的阈值的最小值。

输入格式

第1行输入 N 和 Q，接下来 N 行输入每个通道的阈值，之后 Q 行每行两个整数，对应问题中的 i 和j（i<j）。

输出格式

对于每个问题，输出其结果。

输入数据 1

10 4
75 30 100 38 50 51 52 20 81 5
1 10
3 5
6 9
8 10

Copy

输出数据 1

5
38
20
5