Codeforces Round 271 (Div. 2) |
---|
Закончено |
Сурок нашел ряд из n столбов. Высота i-ого столба равняется hi метрам. Начиная с некоторого столба i1, Сурок хочет пропрыгать по столбам i2, ..., ik. (1 ≤ i1 < i2 < ... < ik ≤ n). Сурок может перепрыгнуть со столба i на столб j, только если i < j и |hi - hj| ≥ d, где |x| — абсолютное значение числа x.
Сурок просит вас найти последовательность прыжков максимальной длины и вывести её.
В первой строке записано два целых числа n и d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).
Во второй строке записано n чисел h1, h2, ..., hn (1 ≤ hi ≤ 1015).
В первой строке должно быть записано одно целое число k — максимальная длина последовательности прыжков.
Во второй строке должно быть записано k целых чисел i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) — номера столбов из максимально длинной последовательности прыжков.
Если есть несколько последовательностей прыжков максимальной длины, выведите любую из них.
5 2
1 3 6 7 4
4
1 2 3 5
10 3
2 1 3 6 9 11 7 3 20 18
6
1 4 6 7 8 9
В первом примере Сурок выбирает столбы 1, 2, 3, 5 с высотами 1, 3, 6, 4. Ещё одна последовательность прыжков длины 4 такова: 1, 2, 4, 5.
Название |
---|