Description

Consider the integers $0, 1, \cdots, N-1$. A transformation sequence $T$ maps $i$ to $T_i$, where $T_i \in \{ 0,1,\cdots, N-1\}$ and $\bigcup_{i=0}^{N-1} \{T_i\} = \{0,1,\cdots , N-1\}$. For all $x, y \in \{0,1,\cdots , N-1\}$, define the distance between $x$ and $y$ as $D(x,y)=\min\{|x-y|,N-|x-y|\}$. Given each $D(i,T_i)$, you need to find a transformation sequence $T$ that satisfies the requirements. If there are multiple valid sequences, output the lexicographically smallest one.

Note: For two transformation sequences $S$ and $T$, if there exists $p < N$ such that for $i = 0, 1, \cdots, p-1$, $S_i = T_i$ and $S_p < T_p$, then we say $S$ is lexicographically smaller than $T$.

Input Format

The first line contains a positive integer $N$, the length of the sequence. The next line contains $N$ integers $D_i$, where $D_i$ denotes the distance between $i$ and $T_i$.

Output Format

If at least one valid transformation sequence $T$ exists, output one line with $N$ integers, which is the lexicographically smallest $T$ you computed; otherwise output No Answer. Note that adjacent numbers are separated by a single space, and there is no trailing space at the end of the line.

5
1 1 2 2 1

1 2 4 0 3

Hint

• For 30% of the testdata: $N \le 50$.
• For 60% of the testdata: $N \le 500$.
• For 100% of the testdata: $N \le 10^4$.

Translated by ChatGPT 5