Historical Research

JOI Spring Training Camp 2013/14
Original Statement / Submission Site

Problem Statement

A diary believed to have been written by inhabitants of ancient IOI Country has been delivered to Professor JOI, a leading researcher in the history of IOI Country. To study life in ancient IOI Country, Professor JOI has decided to investigate the events recorded in the diary.

The diary records exactly one event for each of N days. Events are classified into several types. The type of the event on day i is represented by the integer Xi. A larger value of Xi is considered to represent an event of greater scale.

Professor JOI will analyze the diary in the following way:

1. Select a consecutive period of days from the N days in the diary.
2. For each event type t, define its importance as t × (the number of events of type t during the selected period).
3. Compute the importance of every event type and take the maximum value.

You have been asked by Professor JOI to write a program for this analysis. Given a period to analyze, the program must determine the maximum importance among all event types.

Task

Given the event types for the N days in the diary and Q queries, each representing a period in the diary, determine the maximum importance for each query.

Input

The input is given from standard input in the following format:

N Q
X1 X2 ... XN
A1 B1
A2 B2
...
AQ BQ

• The first line contains two integers N and Q, representing the number of days in the diary and the number of queries.
• The second line contains N integers X1, ..., XN. The integer Xi represents the type of the event on day i.
• Each of the next Q lines contains two integers Aj and Bj. The j-th query concerns the period from day Aj through day Bj, inclusive.

Output

Print Q lines.

On the j-th line, print the maximum importance for the j-th query.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ Q ≤ 100000
• 1 ≤ Xi ≤ 1000000000
• 1 ≤ Aj ≤ Bj ≤ N

Subtasks

Subtask 1 [5 points]

• N ≤ 100
• Q ≤ 100

Subtask 2 [10 points]

• N ≤ 5000
• Q ≤ 5000

Subtask 3 [25 points]

There do not exist distinct queries i and j such that

Ai ≤ Aj ≤ Bj ≤ Bi.

Subtask 4 [60 points]

There are no additional 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 of Sample 1

• The diary consists of 5 days, and the event types appearing in it are 7, 8, and 9.
• For days 1 through 2, the importance of type 7 is 7 × 0 = 0, the importance of type 8 is 8 × 1 = 8, and the importance of type 9 is 9 × 1 = 9. Therefore, the maximum is 9.
• For days 3 through 4, the importance of type 7 is 7 × 1 = 7, the importance of type 8 is 8 × 1 = 8, and the importance of type 9 is 9 × 0 = 0. Therefore, the maximum is 8.
• For day 4 alone, the importance of type 7 is 7 × 0 = 0, the importance of type 8 is 8 × 1 = 8, and the importance of type 9 is 9 × 0 = 0. Therefore, the maximum is 8.
• For days 1 through 4, the importance of type 7 is 7 × 1 = 7, the importance of type 8 is 8 × 2 = 16, and the importance of type 9 is 9 × 1 = 9. Therefore, the maximum is 16.
• For days 2 through 4, the importance of type 7 is 7 × 1 = 7, the importance of type 8 is 8 × 2 = 16, and the importance of type 9 is 9 × 0 = 0. Therefore, the maximum is 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 of Sample 2

This input satisfies the constraints of Subtask 3.

Sample 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

Sample Output 3

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