PEG Judge - NOI '09 - Transformed Sequence

National Olympiad in Informatics, China, 2009

Day 1, Problem 1 - Transformed Sequence

For N integers 0, 1, …, N−1, a transformed sequence T can change i to T_i, where T_i ∈ {0, 1, …, N−1} and ∪_{i = 0}^N−1 { T_i } = {0, 1, …, N−1}. ∀x, y ∈ {0, 1, …, N−1}, define the distance between x and y to be D(x, y) = min{|x − y|, N − |x − y|}. Given the distance D(i, T_i) between each i and T_i, you must determine a transformed sequence T that satisfy the requirements. If many sequences satisfy the requirements, then output the lexicographically smallest one.

Note: For two transformed sequences S and T, if there exists a p < N that satisfies S_i = T_i and S_p < T_p for i = 0, 1, …, p−1, then we say that S is lexicographically smaller than T.

Input Format

The first line of input contains a single integer N, the length of the sequence. The following line contains N integers D_i, where D_i is the distance between i and T_i.

Output Format

If there exists at least one transformed sequence T, then output one line containing N integers, representing the lexicographically smallest transformed sequence T. Otherwise, output "No Answer" (without quotes). Note: Pairs of adjacent numbers in the output must be separated by a single space, and there cannot be trailing spaces.