中国のブログで見た解法。

TLE解法

まず、数列のとりうる値が大きいので、座標圧縮をしておく。そして、次のような配列をもっておく。

$cnt_{i}$ : 今見ている区間に対する、座標圧縮後の値 $i$ の出現回数
$z_{i}$ : $i$ の圧縮前の値

また、区間 $\lbrack l, r)$ に対する $cnt_{i}$ の値を $cnt_{i} (l, r)$ とすると、クエリ $\lbrack l, r)$ に対する答え $f (l, r)$ は、

$f(l, r) = \max ( z_{i} \cdot cnt_{i} ( l, r) )$

になる。
$z_{i} \cdot cnt_{i} ( l, r)$ の値をmultisetで管理すると、最大値の取得、区間の伸縮が $O(\log N)$ で行えるので、Mo's algorithmを使うことによって、全体で $O( ( N + Q) \sqrt{N} \log N)$ で問題を解くことができる。
この解法を実装するとTLEしてしまった(定数倍が小さければ通るかもしれない)。

atcoder.jp

計算量改善

上の解法のネックは、区間を縮める操作に対応するためにすべての値をmultisetで持っておく必要があるところ。区間を広げる操作のみを行えば、解は単調に増加するので最大値以外を持っておく必要がない。
そこで、Moを少し改変してみることにする。左端を $\sqrt{N}$ ずつのブロックに分け、ブロックが同じところでは右端でソートするというところまでは同じ。
ただし、クエリの処理はブロックごとに独立に行う(リセットする)ことにする。こうすると、 $r$ は単調増加になるので、右端は考慮しなくてよい。
左端はどうするかというと、初期位置を次のブロックとの境界にしておく。区間の答え $x$ (初期値0)を持っておき、クエリごとに次の順で操作を行う。