2386 - 超级记忆力

题目描述

小A同学拥有无与伦比的超级记忆力,他可以一次性记住很多数字。

为了考验一下小A同学的记忆力,王老师一次性给小A展示了 N 个整数。然后问了他 M 个问题,每个问题给定一个区间,要求小A同学说出这个区间中的最大数是多少?

为方便老师检验小A同学的答案是否正确,请你先编程求出正确的答案。

输入

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

接下来一行为 N 个数;

接下来 M 行,每行都有两个整数 X,Y 表示询问的区间。

数据范围:

1≤N≤10^5,1≤M≤10^6,1≤X≤Y≤N。数字不超过 C/C++ 的 int 范围。

输出

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

样例

输入

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

输出

5
8
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题