Young Luka is about to enter a house with the evil witch Marica inside. As soon as he enters the house, she asks him questions about her array of $N$ numbers. Luka fearfully asks for a clarification of the questions. Marica explains to him that each query consists of two integers $L$ and $R$ which represent the positions of a contiguous sub-array in her array.

It is Luka's task to answer for each query what the longest contiguous sub-array of that contiguous sub-array (it can be the entire sub-array) having the property of being magical. An array is called magical if all the values are between the values of the first and last number in that array. For example, $[13124]$ is magical, the same as $[41121]$, whereas $[3341]$ is not magical.

Input

The first line of input contains the integer $N$ $(1\le N\le 500000)$, the number of numbers in the array.

The second line contains $N$ integers $a_i$ $(1\le a_i\le {10}^9)$.

The third line contains the integer $Q$ $(1\le Q\le 500000)$, the number of queries.

Each of the following $Q$ lines contains two integers, $L$ and $R$ $(1\le L\le R\le N)$, representing the sub-array from the query.

Output

The $i^{th}$ line of output must contain a single integer – the answer to the $i^{th}$ query.

Scoring

In test cases worth $50\mathrm{\%}$ of total points, it will hold $N,Q\le 30000$.

Sample Input 1

5
5 4 3 3 2
3
1 2
1 1
2 4

Sample Output 1

2
1
3

Sample Input 2

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

Sample Output 2

2
2
4