Historical

Professor JOI is the first ever researcher of the history of IOI country. Today, a diary written by the ancient citizens of IOI country has arrived. To study the living conditions in ancient IOI, professor JOI has decided to investigate the events written in the diary.

Within the N days recorded in the diary, events are recorded one day at a time. Events are classified into several types. The event that happened on the i^th day (1 ≤ i ≤ N) is represented by an integer X_i. You can consider events with high X_i to be bigger events.

Professor JOI has decided to analyse the diary in the following manner:

• We will analyse a certain period of time. The period of time will be a consecutive set of days within the N days recorded in the diary.
• The importance of event type t in the period is defined as t * (the number of time an event of type t occurred in the research period).
• Of all the types of events, we want to find the importance of the type of event with the maximum importance.

You have been ordered to write a program to help Professor JOI with his analysis. Given the N days recorded in the diary and Q research periods Professor JOI wants to analyse, find the maximum importance in each of the research periods.

Input

Read from standard input.

• On the first line, there are two integers N and Q. N is the number of days recorded in the diary and Q is the number of research periods you are to analyse.
• On the next line, there are N integers X_i, ..., X_N. X_i (1 ≤ i ≤ N) is the type of the event that occured on the i^th day.
• Of the next Q lines, the j^th line (1 ≤ j ≤ Q) contains two integers A_j and B_j (1 ≤ A_j ≤ B_j ≤ N). This means the j^th research period is from the A_j^th to the B_j^th day.

Output

Output to standard output.

• On the j^th line, print the one integer representing the maximum importance in the j^th research period.

Constraints

All test cases satisfy the following constraints.

• 1 ≤ N ≤ 100 000.
• 1 ≤ Q ≤ 100 000.
• 1 ≤ X_i ≤ 1 000 000 000. (1 ≤ i ≤ N).

Subtasks

Subtask 1 (5 points):

The following constraints are satisfied.

• N ≤ 100.
• Q ≤ 100.

Subtask 2 (10 points):

The following constraints are satisfied.

• N ≤ 5000.
• Q ≤ 5000.

Subtask 3 (25 points):

i and j such that A_i ≤ A_j ≤ B_j ≤ B_i (1 ≤ i ≤ Q, 1 ≤ j ≤ Q, i ≠ j) do not exist in the input.

Subtask 4 (60 points):

No further constraints.

Sample Input 1

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

Sample Output 1

9
8
8
16
16

Explanation

The diary is 5 days long and contains only events of type 7, 8 and 9.

• From days 1 to 2, event type 7 is of importance 7 * 0 = 0, event type 8 is of importance 8 * 1 = 8, and event type 9 is of importance 9 * 1 = 9. The maximum importance event type has importance 9.
• From days 3 to 4, event type 7 is of importance 7 * 1 = 7, event type 8 is of importance 8 * 1 = 8, and event type 9 is of importance 9 * 0 = 0. The maximum importance event type has importance 8.
• From days 4 to 4, event type 7 is of importance 7 * 0 = 0, event type 8 is of importance 8 * 1 = 8, and event type 9 is of importance 9 * 0 = 0. The maximum importance event type has importance 8.
• From days 1 to 4, event type 7 is of importance 7 * 1 = 7, event type 8 is of importance 8 * 2 = 16, and event type 9 is of importance 9 * 1 = 9. The maximum importance event type has importance 16.
• From days 2 to 4, event type 7 is of importance 7 * 1 = 7, event type 8 is of importance 8 * 2 = 16, and event type 9 is of importance 9 * 0 = 0. The maximum importance event type has importance 16.

Sample Input 2

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

Sample Output 2

27
18
19
19

Explanation

This test case satisfies the conditions in subtask 3.