У Кристины был массив \(a\) длины \(n\), состоящий из неотрицательных целых чисел.
Она построила новый массив \(b\) длины \(n-1\), такой что \(b_i = \max(a_i, a_{i+1})\) (\(1 \le i \le n-1\)).
Например, пусть у Кристины был массив \(a\) = [\(3, 0, 4, 0, 5\)] длины \(5\). Тогда она сделала следующее:
- Посчитала \(b_1 = \max(a_1, a_2) = \max(3, 0) = 3\);
- Посчитала \(b_2 = \max(a_2, a_3) = \max(0, 4) = 4\);
- Посчитала \(b_3 = \max(a_3, a_4) = \max(4, 0) = 4\);
- Посчитала \(b_4 = \max(a_4, a_5) = \max(0, 5) = 5\).
В результате она получила массив
\(b\) = [
\(3, 4, 4, 5\)] длины
\(4\).
Вам известен только массив \(b\). Найдите любой подходящий массив \(a\), который мог быть у Кристины изначально.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите ровно \(n\) целых неотрицательных чисел — элементы массива \(a\), который был у Кристины изначально.
Если возможных ответов несколько — выведите любой из них.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных мы действительно можем получить из массива \(a\) = [\(2, 2, 1, 1\)] массив \(b\) = [\(2, 2, 1\)]:
- \(b_1 = \max(a_1, a_2) = \max(2, 2) = 2\);
- \(b_2 = \max(a_2, a_3) = \max(2, 1) = 2\);
- \(b_3 = \max(a_3, a_4) = \max(1, 1) = 1\).
В третьем наборе входных данных все элементы массива \(b\) являются нулями. Так как каждый \(b_i\) — максимум из двух соседних элементов массива \(a\), то массив \(a\) может состоять только целиком из нулей.
В четвертом наборе входных данных мы действительно можем получить из массива \(a\) = [\(0, 0, 3, 4, 3, 3\)] массив \(b\) = [\(0, 3, 4, 4, 3\)]:
- \(b_1 = \max(a_1, a_2) = \max(0, 0) = 0\);
- \(b_2 = \max(a_2, a_3) = \max(0, 3) = 3\);
- \(b_3 = \max(a_3, a_4) = \max(3, 4) = 4\);
- \(b_4 = \max(a_4, a_5) = \max(4, 3) = 4\);
- \(b_5 = \max(a_5, a_6) = \max(3, 3) = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
5
3 4 4 5
4
2 2 1
5
0 0 0 0
6
0 3 4 4 3
2
10
4
3 3 3
5
4 2 5 5
4
3 3 3
4
2 1 0
3
4 4
6
8 1 3 5 10
|
3 0 4 0 5
2 2 1 1
0 0 0 0 0
0 0 3 4 3 3
10 10
3 3 3 1
4 2 2 5 5
3 3 3 3
2 1 0 0
2 4 4
8 1 1 3 5 10
|