#5040. 未来研究

内存限制:512 MiB 时间限制:10 Sec

题目描述

GX国未来研究的第一人--Hfu教授,最近获得了一份被认为是未来LY国的住民写下的日记。Hfu教授为了通过这份日
记来研究未来LY国的生活,开始着手调查日记中记载的事件。日记中记录了连续N天发生的时间,大约每天发生一
件。事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。Hfu教
授决定用如下的方法分析这些日记:
1. 选择日记中连续的一些天作为分析的时间段
2. 事件种类t的重要度为t*(这段时间内为t的事件数)
3. 计算出所有事件种类的重要度,输出其中的最大值
现在你被要求制作一个帮助Hfu教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入格式

第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。
接下来一行N个空格分隔的整数X1...XN,Xi表示第i天发生的事件的种类
接下来Q行,第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi,表示第i次询问的区间为[Ai,Bi]。
询问保证不会存在Ai<Aj<Bi<=Bj的情况,且对于任意的i,j不会有Bi==Aj,Ai==Aj。
1<=N<=55*10^4
1<=Q<=4*10^5
1<=Xi<=10^9 (1<=i<=N)

输出格式

输出Q行,第i行(1<=i<=Q)一个整数,表示第i次询问的最大重要度

样例

样例输入


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

样例输出


			
9
8
8
5

数据范围与提示