P14420 [JOISC 2014] 历史的研究 / Historical Research

作为研究 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$ 个查询对应区间内事件重要度的最大值。

### 样例 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 完成