Корови Фермера Джона вирішили запропонувати змагання з програмування корів фермера Нхоя. Для того, щоб зробити завдання краще, вони витратили значну кількість на підготовку тестів. Зокрема, для одного із завдань їм знадобилася Ваша допомога.

Є масив відсортованих чисел \(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}\).

Можна довести, що це завжди можливо. Допоможіть коровам ФД вирішити це завдання.

Формат вхідних даних

Перший рядок введення містить \(N\). Наступний рядок містить \(j_1,j_2,\ldots,j_N\).

Формат вихідних даних

Виведіть \(K\), потім \(x_1,\ldots,x_N\) на окремих рядках. Будь-який коректний висновок буде прийнято.

Приклад вхідних даних

6
2 2 4 5 6 6

Приклад вихідних даних

6
1
6
17
22
27
32

Виведено масив \(a = [1, 6, 17, 22, 27, 32]\) і \(K = 6\). \(j_1 = 2\) задоволено, тому що \(a_2 = 6 \leq 1 + 6 = a_1 + K\) але \(a_3 = 17 > 1 + 6 = a_1 + K\), тому \(a_2\) найбільший елемент трохи більше \(a_1\). Аналогічно

• \(j_2 = 2\) задоволено, тому що \(a_2 = 6 \leq 6 + 6\) але \(a_3 = 17 > 6 + 6\)
• \(j_3 = 4\) задоволено, тому що \(a_4 = 22 \leq 17 + 6\) але \(a_5 = 27 > 17 + 6\)
• \(j_4 = 5\) задоволено, тому що \(a_5 = 27 \leq 22 + 6\) але \(a_5 = 32 > 22 + 6\)
• \(j_5 = 6\) задоволено, тому що \(a_6 = 32 \leq 27 + 6\) і \(a_6\) останній елемент масиву
• \(j_6 = 6\) задоволено, тому що \(a_6 = 32 \leq 32 + 6\) і \(a_6\) останній елемент масиву

Це не єдиний можливий коректний висновок для цього введення. Наприклад, Ви можете вивести масив \([1, 2, 4, 5, 6, 7]\) та \(K = 1\).

SCORING:

• Для 50% всіх тестів, N≤5000
• Для тестів, що залишилися, немає додаткових обмежень.

Автор: Danny Mittal