Volleyball

Time limit2sMemory limit1024 MB

Summary

Given n pole heights and m intervals, find for each interval the longest distance between two poles of equal height with no taller pole between them.

Level: Medium7 of 10
Topics: Divide and conquer, Array, Stack
Solved: No attempts yet

Statement

During a PE class, Foma has to leave school on an urgent errand. So that the children do not wander around the school and reveal his absence, he gives them a task.

There are $n$ poles in a row, spaced 1 meter apart. The $i$ -th pole has height $a_i$ . A volleyball net can be strung between two poles if their heights are equal and no pole between them is taller. Each student is assigned an interval of poles and must find the longest net that can be strung within that interval. The length of a net is the distance between the two poles it connects.

The students know this will take them a long time, so they ask you for help.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le m \le 2 \cdot 10^5$ ), the number of poles and the number of students. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ), the heights of the poles. Each of the next $m$ lines contains two integers $l$ and $r$ ( $1 \le l \le r \le n$ ), the interval assigned to one student.

Output

Print $m$ lines. The $i$ -th line contains the answer for the $i$ -th student.

Examples2

Example 1
Input
```
5 3
3 2 1 2 3
1 5
1 4
3 5
```
Expected output
```
4
2
0
```

Example 2

Input

6 4
6 3 6 3 2 3
4 4
2 4
3 6
1 6

Expected output