歴史の研究

#### 题目描述 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://atcoder.jp/contests/joisc2014/tasks/joisc2014_c

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