4241 - 历史研究

IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。 日记中记录了连续N天发生的时间,大约每天发生一件。 事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示,Xi越大,事件的规模就越大。 JOI教授决定用如下的方法分析这些日记:

  1. 选择日记中连续的一些天作为分析的时间段
  2. 事件种类t的重要度为t*(这段时间内重要度为t的事件数)
  3. 计算出所有事件种类的重要度,输出其中的最大值 现在你被要求制作一个帮助教授分析的程序,每次给出分析的区间,你需要输出重要度的最大值。

输入

第一行两个空格分隔的整数N和Q,表示日记一共记录了N天,询问有Q次。 接下来一行N个空格分隔的整数X1...XN,Xi表示第i天发生的事件的种类 接下来Q行,第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi,表示第i次询问的区间为[Ai,Bi]。

输出

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

样例

输入

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

输出

9
8
8
16
16

输入

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

输出

27
18
19
19

输入

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

输出

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15

提示

1<=N<=10^5

1<=Q<=10^5

1<=Xi<=10^9 (1<=i<=N)

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题