Lady and the Permutation of Kozak Vus

Cossack Vus possesses a strategically crucial permutation a of length 2 · n − 1. He encrypts this permutation using an array b, where each element b[i] represents the median† of the subarray a[1], a[2], ..., a[2·i−1]. Lady intercepted this encryption and now seeks your help to determine any permutation that corresponds to this encryption.

Input Format

The first line contains a single integer n (1 ≤ n ≤ 100,000) — the size of the encryption.

The second line contains n integers b[1], b[2], ..., b[n] (1 ≤ b[i] ≤ 2·n−1) — the medians.

It is guaranteed that the input tests are such that a solution always exists.

Output Format

Output 2 · n − 1 integers a[1], a[2], ..., a[2·n−1] on a single line. If multiple solutions exist, you may output any one of them.

Examples

Note

In the first example:

• b[1] = 1 — median of the array (1)

• b[2] = 3 — median of the array (1, 3, 9)

• b[3] = 3 — median of the array (1, 3, 9, 2, 8)

• b[4] = 4 — median of the array (1, 3, 9, 2, 8, 4, 7)

• b[5] = 5 — median of the array (1, 3, 9, 2, 8, 4, 7, 5, 6)

A permutation of length k is a sequence of integers from 1 to k, where each number appears exactly once.

The median of an array of odd length is the element that is in the middle when the array is sorted.