IOI 国の歴史の研究の第一人者であるジョイ教授のもとに，古代の IOI 国の住民が書いたとされる日記が届いた．ジョイ教授はこの日記から古代の IOI 国における生活を研究するため，日記に書かれている出来事を調査することにした．

この日記では $N$ 日間に起きた出来事がそれぞれ 1 日あたり 1 つずつ書かれている．出来事は何種類かに分類されている．$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,\ldots,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 \le N \le 100\,000$．
• $1 \le Q \le 100\,000$．
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$)．

小課題

小課題 1 [5 点]

以下の条件を満たす．

• $N \le 100$．
• $Q \le 100$．

小課題 2 [10 点]

以下の条件を満たす．

• $N \le 5\,000$．
• $Q \le 5\,000$．

小課題 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 点]

追加の制限はない．

入出力例

入力 1

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

出力 1

9
8
8
16
16

注記

• この日記は 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$ である．

入力 2

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

出力 2

27
18
19
19

注記

この入力は小課題 3 の制約を満たしている．

入力 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

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15