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, ~[1\,3\,1\,2\,4]~ is magical, the same as ~[4\,1\,1\,2\,1]~, whereas ~[3\,3\,4\,1]~ is not magical.

Input

The first line of input contains the integer ~N~ ~(1 \le N \le 500\,000)~, 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 500\,000)~, 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\%~ of total points, it will hold ~N, Q \le 30\,000~.

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