eolymp
bolt
Try our new interface for solving problems
Məsələlər

Военный парад

Военный парад

В честь Дня Независимости Байтландии правительство страны решило организовать военный парад. В воинскую часть почетного караула Байтландии пришёл приказ подготовить торжественную шеренгу солдат. Руководство части, в которой уже много лет исправно служит капитан Килобайтин, доверило это ответственное поручение именно ему. Капитану известно, что всего в части служат \textbf{N} солдат, рост каждого \textbf{i}-го (\textbf{1} ≤ \textbf{i} ≤ \textbf{N}) солдата равен \textbf{Н_\{i \}}нанометров. Шеренгой будем называть любую последовательность целых чисел \textbf{A_i}, таких, что \textbf{1} ≤ \textbf{A_i} ≤ \textbf{N }и \textbf{A_i} ≠ \textbf{A_j}, если \textbf{i }≠ \textbf{j}. Длина шеренги -- это длина соответствующей последовательности. Шеренга называется торжественной, если разница в росте любых двух стоящих рядом солдат отличается не более чем на \textbf{K} нанометров. То есть если для последовательности \textbf{A_i} длиной \textbf{M} выполняется правило, что для любого \textbf{1} ≤ \textbf{i} ≤ \textbf{M}-\textbf{1} верно |\textbf{H_Ai} - \textbf{H_Ai_\{+1\}}| ≤ \textbf{K}. \includegraphics{https://static.e-olymp.com/content/8c/8ce5d1bad8ea3cfa42a3301b082612983de6cdd2.jpg} \textit{Рисунок №1.Описание второго примера.} Капитан полагает, что получение им нового воинского звания напрямую зависит от длины подготовленной им торжественной шеренги. Ваша задача -- помочь капитану Килобайтину выполнить приказ и подготовить торжественную шеренгу максимально возможной длины. \InputFile Первая строка входного файла содержит два натуральных числа, разделенные одиночным пробелом \textbf{N} (\textbf{2} ≤ \textbf{N} ≤\textbf{10^5}) и \textbf{K }(\textbf{0} ≤ \textbf{K_\{ \}}≤\textbf{ 10^9}) соответственно. Вторая строка входного файла содержит ровно \textbf{N} целых чисел \textbf{H_i }(\textbf{1} ≤ \textbf{H_i_\{ \}}≤\textbf{ 10^9}) -- рост \textbf{i}-го солдата. Числа разделены одиночными пробелами. Солдаты нумеруются последовательно в порядке их ввода начиная с единицы. \OutputFile Первая строка выходного файла должна содержать одно число \textbf{M} -- максимальную длину торжественной шеренги. Вторая строка выходного файла должна описывать торжественную шеренгу и содержать \textbf{M} целых чисел \textbf{A_i}, числа должны быть разделены одиночными пробелами. Солдаты нумеруются последовательно в порядке их ввода. Если решений несколько, то выведете любое из них.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3 20
1830 1800 1700
Çıxış verilənləri #1
1
2