\(7^{th}\) round, March \(5^{th}\) 2016
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 s\(ub-ar\)ray in her array.
It is Luka’s task to answer for each query what the longest contiguous s\(ub-ar\)ray of that contigu-
ous s\(ub-ar\)ray (it can be the entire s\(ub-ar\)ray) 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@@RISE_MATH_BLOCK_0@@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
s\(ub-ar\)ray from the query.

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

생성자가 기록되지 않았습니다.

출처 COCI 2015/2016 Contest 7