Тёма и Вика играют в следующую игру.
Сперва Вика придумывает последовательность натуральных чисел \(a\) длины \(m\) и выписывает её на листочек. Затем она берёт новый листочек и выписывает на него последовательность \(b\) по следующему правилу:
- Сначала выписывается \(a_1\)
- Затем только такие \(a_i\) (\(2 \le i \le m\)), что \(a_{i - 1} \le a_i\), обозначим длину этой последовательности как \(n\).
Так, например из последовательности \(a=[4, 3, 2, 6, 3, 3]\), Вика получит последовательность \(b=[4, 6, 3]\).
После чего она отдаёт листочек с последовательностью \(b\) Тёме. Он в свою очередь пытается угадать последовательность \(a\).
Тёма считает победу в такой игре очень маловероятной, но всё же хочет найти хотя бы одну последовательность \(a\), которая могла бы быть изначально загадана Викой. Помогите ему и выведите любую такую последовательность.
Обратите внимание, что длина выводимой вами последовательности не должна превышать последовательность из входных данных более, чем в два раза.
Выходные данные
Для каждого набора входных данных выведите две строки. В первой из них выведите одно натуральное число \(m\) — длину последовательности (\(n \le m \le 2 \cdot n\)). Во второй строке выведите \(m\) натуральных чисел \(a_1, a_2, a_3, \dots, a_m\) (\(1 \le a_i \le 10^9\)) — предполагаемая последовательность, которую Вика могла записать на первом листочке.
Если существует несколько подходящих последовательностей, вы можете вывести любую из них.
Примечание
Первый пример разобран в условии.
Во втором примере, Вика могла загадать исходную последовательность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
4 6 3
3
1 2 3
5
1 7 9 5 7
1
144
2
1 1
5
1 2 2 1 1
|
6
4 3 2 6 3 3
3
1 2 3
6
1 7 9 3 5 7
1
144
2
1 1
6
1 2 2 1 1 1
|