## NOI '09 P1 - Transformed Sequence

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
##### National Olympiad in Informatics, China, 2009

For integers , a transformed sequence can change to , where and . , define the distance between and to be . Given the distance between each and , you must determine a transformed sequence that satisfy the requirements. If many sequences satisfy the requirements, then output the lexicographically smallest one.

Note: For two transformed sequences and , if there exists a that satisfies and for , then we say that is lexicographically smaller than .

#### Input Specification

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

#### Output Specification

If there exists at least one transformed sequence , then output one line containing integers, representing the lexicographically smallest transformed sequence . Otherwise, output No Answer.

Note: Pairs of adjacent numbers in the output must be separated by a single space, and there cannot be trailing spaces.

#### Sample Input

5
1 1 2 2 1

#### Sample Output

1 2 4 0 3

#### Constraints

For 20% of the test data, .
For 60% of the test data, .
For 100% of the test data, .

Problem translated to English by Alex.

## Comments

There are no comments at the moment.