AT_joisc2014_c 歴史の研究

IOI 国历史研究的第一人——JOI 教授，最近获得了一份被认为是古代 IOI 国的住民写下的日记。JOI 教授为了通过这份日记来研究古代 IOI 国的生活，开始着手调查日记中记载的事件。 日记中记录了连续 $N$ 天发生的事件，大约每天发生一件。 事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i$ 表示，$X_i$ 越大，事件的规模就越大。 JOI 教授决定用如下的方法分析这些日记： - 选择日记中连续的几天 $[L,R]$ 作为分析的时间段； - 定义事件 $A$ 的重要度 $W_A$ 为 $A\times T_A$，其中 $T_A$ 为该事件在区间 $[L,R]$ 中出现的次数。 现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，**并输出其重要度**。 注意：教授有多组询问。

无

无

对于 $100\%$ 的数据，$1\le Q,N\le 10^5$，$1\le X\le 10^9$，$1\le L\le R\le 10^5$。