题目描述

作为研究 IOI 国历史的先驱者，乔伊教授获得了一本据称由古代 IOI 国居民所写的日记。乔伊教授计划通过分析这本日记来研究古代 IOI 国的生活，因此决定调查日记中记录的事件。

日记中记录了连续 $N$ 天内每天发生的事件，每个事件被分类为若干种类型之一。第 $i$ 天（$1 \le i \le N$）发生的事件类型由整数 $X_i$ 表示，$X_i$ 的值越大，表示该事件的规模越大。

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

1. 从日记的 $N$ 天中选择一个连续的若干天作为分析区间。
2. 对于事件类型 $t$，其“重要度”定义为 $t \times$（该区间内类型 $t$ 的事件数量）。
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$ 个查询对应区间内事件重要度的最大值。

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

提示

样例 1 解释

• 此日记共持续 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。

限制

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

• $1 \le N \le 100000$。
• $1 \le Q \le 100000$。
• $1 \le X_i \le 1000000000$（$1 \le i \le N$）。

子任务

子任务 1 [5 分]

满足以下条件：

• $N \le 100$。
• $Q \le 100$。

子任务 2 [10 分]

满足以下条件：

• $N \le 5000$。
• $Q \le 5000$。

子任务 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 \ne j$）。

子任务 4 [60 分]

无额外限制。

翻译由 Qwen3-235B 完成