题目描述

输入一串数字，给你M个询问，每次询问给你两个数字X，Y，要求你说出X到Y这段区间内的最大数。

输入格式

第一行两个整数N，M(1≤N≤10^5, 1≤M≤10^6)，表示数字的个数和要询问的次数；

接下来一行为N个数；

接下来M行，每行都有两个整数X，Y(1≤X≤Y≤N)。

数列和不超过2^31-1。

输出格式

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

输入/输出样例

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

5
8

说明/提示

时间1000ms，内存256MiB