#BZOJ4241. 历史研究
-
ID: 2834
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
历史研究
No submission language available for this problem.
题目描述
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
数据范围与约定
1<=N<=10^5
1<=Q<=10^5
1<=Xi<=10^9 (1<=i<=N)