研究 IOI 國歷史嘅權威ジョイ教授收到一本日記，據講係古代 IOI 國嘅居民寫嘅。為咗透過呢本日記研究古代 IOI 國嘅生活，ジョイ教授決定調查日記記載嘅事件。

呢本日記記載咗 $N$ 日發生嘅事件，每日各一件。事件分成幾種類型。第 $i$ 日（$1\le i\le N$）嘅事件類型以整數 $X_i$ 表示。一般認為 $X_i$ 越大，事件規模就越大。

ジョイ教授決定用以下方法分析日記。

1. 喺日記嘅 $N$ 日入面，揀連續幾日作為分析期間。
2. 將類型 $t$ 嘅事件嘅重要度，定義為 $t\times$（嗰段期間內類型 $t$ 嘅事件數量）。
3. 計算所有事件類型嘅重要度，再求出其中嘅最大值。

ジョイ教授叫你寫一個用嚟分析嘅程式。希望呢個程式可以喺畀定分析期間之後，求出重要度嘅最大值。

任務

畀定日記中 $N$ 日嘅事件類型，同 $Q$ 個表示日記中某段期間嘅查詢，請寫一個程式，對每次查詢求出事件重要度嘅最大值。

輸入格式

從標準輸入讀取以下資料。

• 第一行有兩個以空格分隔嘅整數 $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\le100\,000$。
• $1\le Q\le100\,000$。
• $1\le X_i\le1\,000\,000\,000$（$1\le i\le N$）。

子任務

子任務 1 [5 分]

滿足以下條件。

• $N\le100$。
• $Q\le100$。

子任務 2 [10 分]

滿足以下條件。

• $N\le5\,000$。
• $Q\le5\,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\times0=0$，類型 $8$ 嘅重要度係 $8\times1=8$，類型 $9$ 嘅重要度係 $9\times1=9$，所以最大值係 $9$。
• 第 3 日到第 4 日，類型 $7$ 嘅重要度係 $7\times1=7$，類型 $8$ 嘅重要度係 $8\times1=8$，類型 $9$ 嘅重要度係 $9\times0=0$，所以最大值係 $8$。
• 第 4 日，類型 $7$ 嘅重要度係 $7\times0=0$，類型 $8$ 嘅重要度係 $8\times1=8$，類型 $9$ 嘅重要度係 $9\times0=0$，所以最大值係 $8$。
• 第 1 日到第 4 日，類型 $7$ 嘅重要度係 $7\times1=7$，類型 $8$ 嘅重要度係 $8\times2=16$，類型 $9$ 嘅重要度係 $9\times1=9$，所以最大值係 $16$。
• 第 2 日到第 4 日，類型 $7$ 嘅重要度係 $7\times1=7$，類型 $8$ 嘅重要度係 $8\times2=16$，類型 $9$ 嘅重要度係 $9\times0=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