IOI 국가 역사의 일인자인 조이 교수는 고대 IOI 국가의 주민이 썼다고 전해지는 일기를 입수했습니다. 고대 IOI 국가의 생활을 연구하기 위해 조이 교수는 일기에 기록된 사건들을 조사하기로 결정했습니다.

일기에는 $N$일 동안 발생한 사건들의 기록이 담겨 있으며, 하루에 한 가지 사건이 기록되어 있습니다. 사건들은 여러 종류로 분류됩니다. $i$번째 날($1 \le i \le N$)에 일어난 사건의 종류는 정수 $X_i$로 나타납니다. $X_i$의 값이 클수록 사건의 규모가 더 큰 것으로 알려져 있습니다.

조이 교수는 다음 방법을 사용하여 일기를 분석하기로 결정했습니다:

1. 일기의 $N$일 중 연속된 며칠을 분석 기간으로 선택합니다.
2. 사건 종류 $t$의 중요도는 $t \times (\text{the number of events of type } t \text{ in that period})$로 정의됩니다(즉, $t$에 해당 기간 동안 발생한 종류 $t$인 사건의 수를 곱한 값).
3. 모든 사건 종류에 대해 중요도를 계산하고 그 최댓값을 구합니다.

당신은 조이 교수로부터 이 분석을 위한 프로그램을 작성해 달라는 의뢰를 받았습니다. 프로그램은 분석 기간이 주어졌을 때 중요도의 최댓값을 구할 수 있어야 합니다.

과제

일기의 $N$일 동안의 사건 종류와 일기의 분석 기간을 나타내는 $Q$개의 쿼리가 주어질 때, 각 쿼리에 대해 사건 중요도의 최댓값을 구하는 프로그램을 작성하세요.

입력

표준 입력에서 다음 데이터를 읽으세요:

• 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $Q$가 주어지며, 이는 일기가 $N$일 동안의 기록을 다루고 $Q$개의 쿼리가 있음을 나타냅니다.
• 다음 줄에는 공백으로 구분된 $N$개의 정수 $X_1, \dots, X_N$이 주어지며, 여기서 $X_i$ ($1 \le i \le N$)는 $i$번째 날의 사건 종류를 나타냅니다.
• 다음 $Q$개의 줄(단, $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 \neq 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

참고 1

• 이 일기는 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

참고 2

이 입력은 서브태스크 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