Lexicographically Smallest Valid Sequence

Interview

Time limit1sMemory limit128 MB

Summary
Given a permutation S, construct the lexicographically smallest permutation T where each element differs from the corresponding S element by at most 1.
Level

Medium5 of 10

Topics
Greedy, Array
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

  1. Example 1

    Input
    8
8
5
7
3
6
4
2
1
    Expected output
    7
4
8
2
6
5
3
1