No testdata at current.

Description

给你一个长度为n的数组a，有m次询问，每次给你一个区间(l,r)，请你求出a数组区间(l,r)里的最大值。

Format

Input

第一行两个正整数，n，m。第二行n个整数，表示数组a。后面m行，每行两个正整数，l，r。

Output

m行。对于每次询问，输出答案。

Samples

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

5
4
1
4

Limitation

1s, 1024KiB for each test case. 对于40%的数据，$1≤n,m≤10^3$ 对于100%的数据，$1≤l≤r≤n≤10^5，1≤m≤2*10^6$