Sashko and Smooth Transitions#10254
Sashko is fascinated by smooth transitions. He considers an array to be wonderful if the absolute difference between any two consecutive elements is less than or equal to a given number .
Sashko has an array of integers with length . He can perform only one operation on this array: swap any two elements. He wants to know if he can make the array wonderful by performing this operation, and he needs your help to find out.
The first line contains two integers and (1 \leq n \leq 10^5, 0 \leq k \leq 10^9) — the length of the array and the maximum allowable difference between consecutive elements.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the elements of the array.
Output a single line with two integers separated by a space:
, if it is impossible to make the array wonderful.
, if the array is already wonderful.
, if the array is not wonderful, and you can make it wonderful by swapping the elements at positions and (1 \leq i \neq j \leq n). If there are multiple valid pairs of indices, you can output any one of them.
Note that in the pair of indices, the first number must be less than the second.
Example 1
Example 2
Example 3
In the second example, it would be incorrect to output two non-zero numbers because the array is already wonderful.
In the third example, it is clear that making the array wonderful is impossible.