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

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.

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**(1 ≤_{i}**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**and_{j}**B**(1 ≤_{j}**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 to standard output.

- On the
**j**^{th}line, print the one integer representing the maximum importance in the**j**^{th}research period.

All test cases satisfy the following constraints.

- 1 ≤
**N**≤ 100 000. - 1 ≤
**Q**≤ 100 000. - 1 ≤
**X**≤ 1 000 000 000. (1 ≤_{i}**i**≤**N**).

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}** ≤

Subtask 4 (60 points):

No further constraints.

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

```
9
8
8
16
16
```

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.

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

```
27
18
19
19
```

This test case satisfies the conditions in subtask 3.

Subtask | Score |
---|---|

1 | 5 |

2 | 10 |

3 | 25 |

4 | 60 |

5 | 0 |