Background

It is uncertain whether this problem is included in the Lanqiao Cup 2nd International Contest. The official Lanqiao Cup statement crossed out the problem number, but the problem itself is still kept.

Problem Description

For an ordered signal $s_1, s_2, \ldots, s_n$, each number in the signal is a positive integer. When applying a blur filter to this signal, a new signal $t_1, t_2, \ldots, t_n$ is obtained. The values of the new signal are defined as $t_1 = \lfloor (s_1+s_2)/2 \rfloor$, $t_2 = \lfloor (s_1+s_2+s_3)/3 \rfloor$, $t_3 = \lfloor (s_2+s_3+s_4)/3 \rfloor$, $\ldots$, $t_{n-1} = \lfloor (s_{n-2}+s_{n-1}+s_n)/3 \rfloor$, $t_n = \lfloor (s_{n-1}+s_n)/2 \rfloor$, where $\lfloor x \rfloor$ denotes the greatest integer not exceeding $x$.

Now the blurred signal $t$ is given. Please compute the signal $s$. If there are multiple valid $s$, find the one with the smallest $s_1$. If there are multiple solutions with the same $s_1$, find the one with the smallest $s_2$, and so on. In other words, find the lexicographically smallest sequence $s_1, s_2, s_3, \ldots, s_n$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, which are $t_1, t_2, \ldots, t_n$ in order.

Output Format

Output one line containing $n$ integers, representing $s_1, s_2, \ldots, s_n$ in order. Note that every number in $s$ must be a positive integer.

5
1 2 3 4 5

1 1 4 4 6

Hint

Constraints

For $40\%$ of the test cases, $2 \le n \le 20$, and each number in the signal $t$ is a positive integer not exceeding $100$.

For $60\%$ of the test cases, $2 \le n \le 300$, and each number in the signal $t$ is a positive integer not exceeding $100$.

For all test cases, $2 \le n \le 5000$, and each number in the signal $t$ is a positive integer not exceeding $1000000$.

Please note that the above ranges apply to each number in the signal $t$. Each number in the signal $s$ may exceed this range.

Translated by ChatGPT 5