e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, II Stage, II Round

H. Сашко та плавні переходи

Сашко дуже любить плавні переходи. Зокрема, він вважає чудовими такі масиви, у яких різниця по модулю між будь-якими двома сусідніми числами менша або дорівнює певному числу $k$. Сашко отримав масив цілих чисел довжиною $n$. Він може виконати над ним одну єдину операцію --- поміняти місцями будь-які два числа. Тепер він хоче дізнатись, чи може він за допомогою цієї операції отримати чудовий масив, і просить у вас допомоги. \InputFile Перший рядок містить два цілі числа $n$ і $k$ ($1 \leq n \leq 10^5$, $0 \leq k \leq 10^9$) --- довжина масиву й максимальна допустима різниця між сусідніми числами. Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) --- числа масиву. \OutputFile У єдиному рядку через пробіл виведіть два цілі числа: \begin{itemize} \item $-1$ $-1$, якщо масив неможливо зробити чудовим. \item $0$ $0$, якщо масив уже є чудовим. \item $i$ $j$, якщо масив не є чудовим, а для того, щоб зробити масив чудовим, потрібно поміняти місцями числа на позиціях $i$ та $j$ ($1 \leq i \neq j \leq n$). Якщо існує декілька таких пар індексів, виведіть будь-яку з них. \end{itemize} Зверніть увагу, що в парі індексів перше число має бути меншим за друге. \Note У другому прикладі було б помилкою вивести два ненульових числа, адже масив вже є чудовим. У третьому прикладі легко переконатись, що масив неможливо зробити чудовим.
Time limit 1 second
Memory limit 256 MiB
Input example #1
8 3
5 7 1 9 7 4 6 2
Output example #1
3 7
Input example #2
7 2
5 7 7 6 8 6 4
Output example #2
0 0
Input example #3
7 1
6 7 8 10 9 8 7
Output example #3
-1 -1
Author Andrey Abdulaev