Коровы Фермера Джона решили предложить соревнование по программированию
коровам фермера Нхоя. Для того, чтобы сделать задачи получше, они потратили
значительное количество на подготовку тестов. В частности, для одной из задач
им потребовалась Ваша помощь.
Имеется массив отсортированных чисел \(x_1 \leq x_2 \leq \dotsb \leq x_N\)
(\(1 \leq N \leq 10^5\)), и целое число \(K\). Вы не знаете массив или \(K\)
но Вы знаете для каждого индекса \(i\), наибольший индекс \(j_i\) такой, что
\(x_{j_i} \leq x_i + K\). Гарантируется, что \(i\le j_i\) и \(j_1\le j_2\le \cdots \le j_N\le N\).
По заданной информации коровы ФД должны сконструировать любой массив,
который соответствует данной информации для некоторого целого \(K\).
Конструкция должна удовлетворять условию
\(0 \leq x_i \leq 10^{18}\) для всех \(i\) и \(1 \leq K \leq 10^{18}\).
Можно доказать, что это всегда возможно. Помогите коровам ФД решить эту задачу.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\). Следующая строка содержит \(j_1,j_2,\ldots,j_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(K\), затем \(x_1,\ldots,x_N\) на отдельных строках. Любой корректный вывод
будет принят.
SCORING:
- Для 50% всех тестов, \(N\le 5000\)
- Для оставшихся тестов нет дополнительных ограничений.