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

• 选择日记中连续的几天 [L,R] 作为分析的时间段；
  
• 定义事件 A 的重要度 WA 为 A×TA，其中 TA 为该事件在区间 [L,R] 中出现的次数。
  

现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。
注意：教授有多组询问。

第一行两个空格分隔的整数 N 和 Q，表示日记一共记录了 N 天，询问有 Q 次。
接下来一行 N 个空格分隔的整数表示每天的事件种类。
接下来 Q 行，每行给出 L,R 表示一组询问。

输出共有 Q 行，每行一个整数，表示对应的询问的答案。

样例二：
输入：
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




对于 100% 的数据，1≤Q,N≤10⁵，1≤X≤10⁹，1≤L≤R≤10⁵。

P1494 莫队 数据结构 线段树 树状数组