歴史の研究

题意翻译

#### 题目描述 IOI 国历史研究的第一人——JOI 教授,最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活,开始着手调查日记中记载的事件。 日记中记录了连续 $N$ 天发生的时间,大约每天发生一件。 事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i$ 表示,$X_i$ 越大,事件的规模就越大。 JOI 教授决定用如下的方法分析这些日记: - 选择日记中连续的几天 $[L,R]$ 作为分析的时间段; - 定义事件 $A$ 的重要度 $W_A$ 为 $A\times T_A$,其中 $T_A$ 为该事件在区间 $[L,R]$ 中出现的次数。 现在,您需要帮助教授求出所有事件中重要度最大的事件是哪个,**并输出其重要度**。 注意:教授有多组询问。 #### 输入格式 第一行两个空格分隔的整数 $N$ 和 $Q$,表示日记一共记录了 $N$ 天,询问有 $Q$ 次。 接下来一行 $N$ 个空格分隔的整数表示每天的事件种类。 接下来 $Q$ 行,每行给出 $L,R$ 表示一组询问。 #### 输出格式 输出共有 $Q$ 行,每行一个整数,表示对应的询问的答案。 #### 数据范围 对于 $100\%$ 的数据,$1\le Q,N\le 10^5$,$1\le X\le 10^9$,$1\le L\le R\le 10^5$。

题目描述

[problemUrl]: https://joisc2014.contest.atcoder.jp/tasks/joisc2014_c 問題文は [JOI のウェブサイト](http://www.ioi-jp.org/camp/2014/2014-sp-tasks/index.html) を参照してください。

输入输出格式

输入格式


输出格式


输入输出样例

输入样例 #1

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

输出样例 #1

9
8
8
16
16

输入样例 #2

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

输出样例 #2

27
18
19
19

输入样例 #3

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

输出样例 #3

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