Lexicographically Smallest Valid Sequence

You are given a sequence S of length n. S is a permutation containing every integer from 1 to n exactly once.

Find the lexicographically smallest sequence T that satisfies all of the following conditions.

1. T is also a permutation containing every integer from 1 to n exactly once.
2. For every i, |T_i - S_i| <= 1.

The first line contains the length n of the sequence. (3 <= n <= 50,000)

Each of the next n lines contains one element of S, in order.

Print the lexicographically smallest valid sequence T, one number per line.