Migrated from Lutece 2527 打怪兽

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小虎在玩一个打怪兽的游戏。在这个游戏里，小虎会遇到一排 $n$ 个怪兽，每个怪兽都有一个攻击力，记为 $a_i$ 。在战斗开始前，所有怪兽都不可见。但是小虎有 $m$ 次侦察的机会，每次侦察时，系统会随机给出两个数字 $l_i,r_i$ ，这时编号在 $l_i$ 和 $r_i$ 之间（包含）的怪兽就会显现出来，由于时间有限，小虎需要找出在这些显现的怪兽之中攻击力最高的那个，并把这个攻击力记录下来。每次侦察后怪兽又变为不可见的状态，直至系统给出下一个侦察的区间或者侦察结束。你能帮助小虎确定这 $m$ 个攻击力的值吗？

Input

第一行包含两个整数 $n,m\ (1\le n\le 10^5,1\le m\le 2\times 10^6)$ ，分别表示怪兽的个数和侦察的次数； 第二行包含 $n$ 个整数 $a_i\ (0\le a_i\le 10^9)$，表示每个怪兽的攻击力； 接下来 $m$ 行，每行包含两个整数 $l_i,r_i\ (1\le l_i\le r_i\le n)$，表示第 $i$ 次侦察给出的区间范围 $[l_i,r_i]$ 。

Output

输出包含 $m$ 行，每行一个整数，表示每次询问区间中攻击力的最大值。

Samples

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

1
7
10

Note

在第一个区间 $[1,1]$ 中，最大值为 $1$ ，故输出 $1$； 在第一个区间 $[3,7]$ 中，最大值为 $7$ ，故输出 $7$； 在第一个区间 $[1,10]$ 中，最大值为 $10$ ，故输出 $10$。

Resources

2021 UESTC ICPC Training for Data Structures