9 人解决，20 人已尝试。
12 份提交通过，共有 85 份提交。
7.4 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
For a number $t$ denote as $h(t)$ maximal $k$ such that $t$ is divisible by $2^k$. For example, $h(24) = 3$, $h(5) = 0$. Let $l(t) = 2^{h(t)}$, for example, $l(24) = 8$, $l(5) = 1$.
Consider array $a[1], a[2], \ldots, a[n]$ of integer numbers. Fenwick tree for this array is the array $b[1], b[2], \ldots, b[n]$ such that
$$b[i] = \sum^{i}_{j = i - l(i) + 1} a[j]$$
So
$b[1] = a[1]$,
$b[2] = a[1] + a[2]$,
$b[3] = a[3]$,
$b[4] = a[1] + a[2] + a[3] + a[4]$,
$b[5] = a[5]$,
$b[6] = a[5] + a[6]$,
…
For example, the Fenwick tree for the array $a = (3, -1, 4, 1, -5, 9)$ is the array $b = (3, 2, 4, 7, -5, 4)$.
Let us call an array self-fenwick if it coincides with its Fenwick tree. For example, the array above is not self-fenwick, but the array $a = (0, -1, 1, 1, 0, 9)$ is self-fenwick.
You are given an array $a$. You are allowed to change values of some elements without changing their order to get a new array $a’$ which must be self-fenwick. Find the way to do it by changing as few elements as possible.
The first line of the input file contains $n$ ― the number of elements in the array ($1 \le n \le 100~000$). The second line contains $n$ integer numbers ― the elements of the array. The elements do not exceed $10^9$ by their absolute values.
Output $n$ numbers ― the elements of the array $a’$. If there are several solutions, output any one.
6 3 -1 4 1 -5 9
0 -1 1 1 0 9
9 人解决，20 人已尝试。
12 份提交通过，共有 85 份提交。
7.4 EMB 奖励。