Professor Joy, a leading researcher in the history of the IOI nation, has received a diary believed to have been written by an ancient resident of the IOI nation. To study life in the ancient IOI nation, Professor Joy decided to investigate the events recorded in the diary.

The diary contains records of events that occurred over $N$ days, with one event recorded for each day. Events are classified into several types. The type of event on day $i$ ($1 \le i \le N$) is represented by an integer $X_i$. It is believed that the larger the value of $X_i$, the larger the scale of the event.

Professor Joy decided to analyze the diary using the following method:

1. Choose a consecutive number of days within the $N$ days of the diary as the analysis period.
2. The importance of an event type $t$ is defined as $t \times (\text{the number of events of type } t \text{ in that period})$.
3. Calculate the importance for all event types and find the maximum value.

You have been tasked by Professor Joy to create a program for this analysis. The program should be able to find the maximum importance when given an analysis period.

Task

Given the event types for the $N$ days of the diary and $Q$ queries representing periods in the diary, write a program that finds the maximum importance of events for each query.

Input

Read the following data from standard input:

• The first line contains two integers $N$ and $Q$ separated by a space, representing that the diary covers $N$ days and there are $Q$ queries.
• The next line contains $N$ integers $X_1, \dots, X_N$ separated by spaces, where $X_i$ ($1 \le i \le N$) represents the event type on day $i$.
• Each of the following $Q$ lines (for $1 \le j \le Q$) contains two integers $A_j$ and $B_j$ ($1 \le A_j \le B_j \le N$) separated by a space, representing that the $j$-th query is for the period from day $A_j$ to day $B_j$.

Output

Output $Q$ lines to standard output. The $j$-th line ($1 \le j \le Q$) should contain an integer representing the maximum importance for the $j$-th query.

Constraints

All input data satisfies the following conditions:

• $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$).

Subtasks

Subtask 1 [5 points]

• $N \le 100$.
• $Q \le 100$.

Subtask 2 [10 points]

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

Subtask 3 [25 points]

• There are no $i, j$ ($1 \le i \le Q, 1 \le j \le Q, i \neq j$) such that $A_i \le A_j \le B_j \le B_i$.

Subtask 4 [60 points]

• No additional constraints.

Examples

Input 1

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

Output 1

9
8
8
16
16

Note 1

• This diary consists of 5 days, and the event types recorded are 7, 8, or 9.
• For the period from day 1 to day 2, the importance of event type 7 is $7 \times 0 = 0$, event type 8 is $8 \times 1 = 8$, and event type 9 is $9 \times 1 = 9$. The maximum of these is 9.
• For the period from day 3 to day 4, the importance of event type 7 is $7 \times 1 = 7$, event type 8 is $8 \times 1 = 8$, and event type 9 is $9 \times 0 = 0$. The maximum of these is 8.
• For day 4, the importance of event type 7 is $7 \times 0 = 0$, event type 8 is $8 \times 1 = 8$, and event type 9 is $9 \times 0 = 0$. The maximum of these is 8.
• For the period from day 1 to day 4, the importance of event type 7 is $7 \times 1 = 7$, event type 8 is $8 \times 2 = 16$, and event type 9 is $9 \times 1 = 9$. The maximum of these is 16.
• For the period from day 2 to day 4, the importance of event type 7 is $7 \times 1 = 7$, event type 8 is $8 \times 2 = 16$, and event type 9 is $9 \times 0 = 0$. The maximum of these is 16.

Input 2

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

Output 2

27
18
19
19

Note 2

This input satisfies the constraints of Subtask 3.

Input 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

Output 3

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