IOI 國歷史研究的權威ジョイ教授收到了一本據說由古代 IOI 國居民撰寫的日記。為了透過這本日記研究古代 IOI 國的生活，ジョイ教授決定調查日記中記載的事件。
這本日記記錄了 $N$ 天發生的事件，每天恰好記載一件事。事件分成若干種類。第 $i$ 天（$1 \le i \le N$）的事件種類以整數 $X_i$ 表示。一般認為，$X_i$ 的值越大，事件的規模就越大。
ジョイ教授決定用以下方法分析日記。
- 從日記的 $N$ 天中，選擇連續若干天作為分析期間。
- 將種類 $t$ 的事件的重要度定義為 $t \times$（該期間內種類 $t$ 的事件數量）。
- 計算所有事件種類的重要度，並求出其中的最大值。
ジョイ教授要求你撰寫分析用的程式。這個程式應能在給定分析期間時，求出重要度的最大值。
任務
給定日記中 $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 \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\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