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 ith day (1 ≤ iN) is represented by an integer Xi. You can consider events with high Xi 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

• 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 Xi, ..., XN. Xi (1 ≤ iN) is the type of the event that occured on the ith day.
• Of the next Q lines, the jth line (1 ≤ jQ) contains two integers Aj and Bj (1 ≤ AjBjN). This means the jth research period is from the Ajth to the Bjth day.

Output

Output to standard output.

• On the jth line, print the one integer representing the maximum importance in the jth research period.

Constraints

All test cases satisfy the following constraints.

• 1 ≤ N ≤ 100 000.
• 1 ≤ Q ≤ 100 000.
• 1 ≤ Xi ≤ 1 000 000 000. (1 ≤ iN).

The following constraints are satisfied.

• N ≤ 100.
• Q ≤ 100.

The following constraints are satisfied.

• N ≤ 5000.
• Q ≤ 5000.

i and j such that AiAjBjBi (1 ≤ iQ, 1 ≤ jQ, ij) do not exist in the input.

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.

Submitting .cpp to 'Historical'

Time Limit: 4 Seconds
Memory Limit: 512MB