题目描述

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

输入格式

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

输出格式

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

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

5 38 20 5

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

2 3 1

2 2
494044383 517973870
1 2
1 2

494044383
494044383

数据范围与约定

1≤N≤100000；1≤Q≤100000；1≤每个通道的阈值≤10^9。