作为 IOI 国历史研究的权威，乔伊教授收到了一份据称由古代 IOI 国居民所写的日记。为了研究古代 IOI 国的生活，乔伊教授决定调查日记中记载的事件。

这份日记记录了 $N$ 天内发生的事件，每天记录一件。事件被分为若干种类。第 $i$ 天 ($1 \le i \le N$) 的事件种类用整数 $X_i$ 表示。人们认为 $X_i$ 的值越大，该事件的规模就越大。

乔伊教授决定通过以下方法分析日记：

1. 从日记的 $N$ 天中选择一段连续的时间作为分析周期。
2. 将事件种类 $t$ 的重要度定义为 $t \times (\text{该周期内事件种类 } t \text{ 出现的次数})$。
3. 计算所有事件种类的重要度，并求出其中的最大值。

你受乔伊教授之托编写一个分析程序。该程序需要在给定分析周期时，求出重要度的最大值。

题目描述

给定 $N$ 天的事件种类以及 $Q$ 个表示日记中时间段的查询，请编写一个程序，针对每个查询求出事件重要度的最大值。

输入格式

从标准输入读取以下数据：

• 第 1 行包含两个整数 $N, Q$，以空格分隔。这表示日记记录了 $N$ 天，且有 $Q$ 个查询。
• 下一行包含 $N$ 个整数 $X_1, \dots, X_N$，以空格分隔，其中 $X_i$ ($1 \le i \le N$) 表示第 $i$ 天的事件种类。
• 接下来的 $Q$ 行中的第 $j$ 行 ($1 \le j \le Q$) 包含两个整数 $A_j, B_j$ ($1 \le A_j \le B_j \le N$)，以空格分隔，表示第 $j$ 个查询对应从第 $A_j$ 天到第 $B_j$ 天的周期。

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行 ($1 \le j \le Q$) 输出一个整数，表示第 $j$ 个查询对应的重要度最大值。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

子任务

子任务 1 [5 分] 满足以下条件： $N \le 100$ $Q \le 100$

子任务 2 [10 分] 满足以下条件： $N \le 5\,000$ $Q \le 5\,000$

子任务 3 [25 分] * 不存在满足 $A_i \le A_j \le B_j \le B_i$ 的 $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$)。

子任务 4 [60 分] 没有额外限制。

样例

样例输入 1

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

样例输出 1

9
8
8
16
16

说明

• 该日记记录了 5 天，日记中出现的事件种类为 7, 8, 9 中的任意一种。
• 第 1 天到第 2 天，事件种类 7 的重要度为 $7 \times 0 = 0$，事件种类 8 的重要度为 $8 \times 1 = 8$，事件种类 9 的重要度为 $9 \times 1 = 9$，因此最大值为 9。
• 第 3 天到第 4 天，事件种类 7 的重要度为 $7 \times 1 = 7$，事件种类 8 的重要度为 $8 \times 1 = 8$，事件种类 9 的重要度为 $9 \times 0 = 0$，因此最大值为 8。
• 第 4 天，事件种类 7 的重要度为 $7 \times 0 = 0$，事件种类 8 的重要度为 $8 \times 1 = 8$，事件种类 9 的重要度为 $9 \times 0 = 0$，因此最大值为 8。
• 第 1 天到第 4 天，事件种类 7 的重要度为 $7 \times 1 = 7$，事件种类 8 的重要度为 $8 \times 2 = 16$，事件种类 9 的重要度为 $9 \times 1 = 9$，因此最大值为 16。
• 第 2 天到第 4 天，事件种类 7 的重要度为 $7 \times 1 = 7$，事件种类 8 的重要度为 $8 \times 2 = 16$，事件种类 9 的重要度为 $9 \times 0 = 0$，因此最大值为 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 的限制。

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