#[2874].「JOISC 2014 Day1」历史研究

内存限制：512 MB 时间限制：4000 ms

题目译自 JOISC 2014 Day1 T3「歴史の研究」

IOI 国历史研究的大牛——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。
日记中记录了连续 $N$ 天发生的事件，每天发生一件事件。
事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i$ 表示，$X_i$ 越大，事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记： 1. 选择日记中连续的一些天作为分析的时间段； 2. 事件种类 $t$ 的重要度为 $t$ 与这段时间内重要度为 $t$ 的事件数的乘积； 3. 计算出所有事件种类的重要度，输出其中的最大值。

请制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

第一行两个空格分隔的整数 $N$ 和 $Q$，表示日记一共记录了 $N$ 天，询问有 $Q$ 次。
接下来一行 $N$ 个空格分隔的整数 $X_1\dots X_N$，$X_i$ 表示第 $i$ 天发生的事件的种类。
接下来 $Q$ 行，第 $i$ 行有两个空格分隔整数 $A_i$ 和 $B_i$，表示第 $i$ 次询问的区间为 $[A_i,B_i]$。

输出 $Q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的最大重要度。

这本日记由五天组成，日记中写的事件类型是 $7,8,9$ 之一。

时间区间	事件种类 $7$ 的重要性	事件种类 $8$ 的重要性	事件种类 $9$ 的重要性	$\max$
$[1,2]$	$7×0 = 0$	$8×1 = 8$	$9×1 = 9$	$9$
$[3,4]$	$7×1 = 7$	$8×1 = 8$	$9×0 = 0$	$8$
$[4,4]$	$7×0 = 0$	$8×1 = 8$	$9×0 = 0$	$8$
$[1,4]$	$7×1 = 7$	$8×2 = 16$	$9×1 = 9$	$16$
$[2,4]$	$7×1 = 7$	$8×2 = 16$	$9×0 = 0$	$16$

这组样例属于子任务 #3。

对于所有数据，$1\le N, Q\le 10^5,$ $1\le X_i\le 10^9 (1\le i\le N)$。

子任务编号	分值	附加条件
1	5	$N, Q\le 100$
2	10	$N, Q\le 5000$
3	25	没有 $i, j$ $(1≤i≤Q, 1≤j≤Q, i≠j)$，使得 $A_i≤A_j≤B_j≤B_i$。
4	60	无

样例输入 1

样例输出 1

样例输入 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

样例输出 2

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

2874 「JOISC 2014 Day1」历史研究

题目描述

输入格式

输出格式

样例 1

样例 2

样例 3

数据范围与提示