Author: | ACM ICPC 2008-2009, NEERC, Northern Subregional Contest | Time limit: | 3 sec | |
Input file: | fenwick.in | Memory limit: | 256 Mb | |
Output file: | fenwick.out |
Fenwick tree is a data structure effectively supporting prefix sum queries.
For a number t denote as h(t) maximal k such that t is divisible by 2k. For example, h(24)=3, h(5)=0. Let l(t)=2h(t), for example, l(24)=8, l(5)=1.
Consider array a[1],a[2],…,a[n] of integer numbers. Fenwick tree for this array is the array b[1],b[2],…,b[n] such that
b[i]=∑ij=i−l(i)+1a[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. The second line contains n integer numbers — the elements of the array.
Output n numbers — the elements of the array a′. If there are several solutions, output any one.
1≤n≤100000.
The elements of the input array do not exceed 109 by their absolute values.
No. | Input file (fenwick.in ) |
Output file (fenwick.out ) |
---|---|---|
1 |
|
|