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 .
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 .
If there exists at least one transformed sequence , then output one
line containing integers, representing the lexicographically
smallest transformed sequence . Otherwise, output
Note: Pairs of adjacent numbers in the output must be separated by a single space, and there cannot be trailing spaces.
5 1 1 2 2 1
1 2 4 0 3
For 20% of the test data, .
For 60% of the test data, .
For 100% of the test data, .