After several holiday seasons,
's old Christmas lights aren't looking too good. Some of the bulbs still glow normally, but others are almost completely out. wants to reuse them again next year, but doesn't want his decorations to look too shabby either. individual bulbs. The
bulb has a brightness of
. defines the variance of a contiguous string of bulbs to be the difference in brightness between the brightest and the dimmest bulb in that string. considers a string of bulbs to be consistent if its variance is no greater than
.
queries, each of the following form:
If
considers the string of lights fromto
![]()
to be pretty, which contiguous segment of lights should he keep from
such that the segment is consistent and has the maximum length possible?
Help
keep his decorations beautiful for another year!Constraints
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line of input will contain and
.
The second line will contain space-separated integers,
, the brightness of the bulbs.
The third line will contain .
The next lines will each contain a query in the form
l r
.
Output Specification
Output the answer to each query on a separate line. Each answer should be of the form a b
, where
is the maximum length consistent subarray of
. If there are multiple answers of the same length, output the one with the smallest values of
and
.
Sample Input
7 4
3 6 8 4 3 6 1
3
2 6
3 6
1 3
Sample Output
2 4
4 6
1 2
Explanation for Sample Output
Note that in the first query, both 2 4
and 4 6
have the same length, but we output the smallest possible answers. Similarly, in the third query, 2 3
is the same length but not outputted.
Comments