레이팅 미적용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 contigu-
ous 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.
In test cases worth 50% of total points, it will hold N, Q ⩽30 000.
The first line of input contains the integer \(N\) (1 ⩽\(N\) ⩽500 000), the number of numbers in the array.
The second line contains \(N\) integers \(a_{i}\) (1 ⩽\(a_{i}\) ⩽\(10^{9}\)).
The third line contains the integer \(Q\) (1 ⩽\(Q\) ⩽500 000), the number of queries.
Each of the following \(Q\) lines contains two integers, \(L\) and \(R\) (1 ⩽\(L\) ⩽\(R\) ⩽\(N\)), representing the
sub-array from the query.
The \(i^{th}\) line of output must contain a single integer – the answer to the \(i^{th}\) query.
5
5 4 3 3 2
3
1 2
1 1
2 4
6
6 6 5 1 6 2
3
4 5
4 6
1 4output
2
1
3
2
2
4