题目描述

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

1. 选择日记中连续的一些天作为分析的时间段
2. 事件种类 $t$ 的重要度为 $t \times (这段时间内重要度为t的事件数)$
3. 计算出所有事件种类的重要度，输出其中的最大值 现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

输入格式

第一行两个空格分隔的整数 $N$ 和 $Q$，表示日记一共记录了 $N$ 天，询问有 $Q$ 次。

接下来一行 $N$ 个空格分隔的整数 $X_1 \dots X_N$，$X_i$ 表示第 $i$ 天发生的事件的种类。

接下来 $Q$ 行，第 $i$ 行 $(1\le i \le Q)$ 有两个空格分隔整数 $A_i$ 和 $B_i$，表示第 $i$ 次询问的区间为 $[A_i,B_i]$ 。

输出格式

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

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

9
8
8
16
16

提示

$1 \le N \le 10^5, 1 \le Q \le 10^5, 1 \le X_i \le 10^9 (1 \le i \le N)$

题目来源

JOI 2013~2014 春季training合宿 竞技1 By PoPoQQQ