Background

Special for beginners, ^_^

Description

输入一串数字，给你 $M（1≤M≤10^6）$个询问，每次询问就给你两个数字 $X,Y（1≤X≤Y≤N）$，要求你说出$X$到 $Y$这段区间内的最大数。

Format

Input

第一行两个整数 $N,M$ 表示数字的个数和要询问的次数；

接下来一行为 $N（1≤N≤10^5）$个数；

接下来$M$行，每行都有两个整数 $X,Y$。

Output

输出共 $M$行，每行输出一个数。

Samples

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

`

5
8

Limitation

1s, 1024KiB for each test case.