일렬로 놓인 \(n\)개의 계단 높이 수열 \(A = (A_1, A_2, \dots, A_n)\)가 주어진다.

인접한 두 계단의 높이 차이가 정확히 1일 때만 다음 계단으로 이동할 수 있다.

이동이 불가능한 구간이 생길 수 있기 때문에 계단 사이사이에 양의 정수 높이의 새로운 계단을 추가할 수 있다.

시작점 \(A_1\)에서 도착점 \(A_n\)까지 이동하기 위해서 추가하는 계단의 수가 최소가 되도록 할 때,

계단을 추가한 뒤의 수열을 출력하라.

Definition(정의)

최종적으로 만들어진 수열 \(B = (B_1, B_2, \dots, B_m)\)는 다음을 만족해야 한다.

(1) \(A\)는 \(B\)의 부분 수열이다.

(2) 모든 \(1 \le j < m\)에 대해 \(|B_{j+1} - B_j| = 1\)을 만족해야 한다.

Constrains(제한)

\(1 \le n \le 10\)

\(1 \le A_i \le 25\)

\(A_i \ne A_{i+1}\)이다. (모든 인접 원소들은 서로 다름)

모든 입력은 양의 정수이다.

입력 설명

첫째 줄에 정수 \(n\)이 주어진다.

둘째 줄에 \(A_1, A_2, \dots, A_n\)이 주어진다.

출력 설명

조건을 만족하는 수열을 공백으로 구분하여 출력하여라.

예제 입력 1

3
1 5 2

예제 출력 1

1 2 3 4 5 4 3 2

예제 입력 2

6
3 4 5 6 5 4

예제 출력 2

3 4 5 6 5 4

예제 입력 3

5
22 20 18 16 20

예제 출력 3

22 21 20 19 18 17 16 17 18 19 20