Məsələlər
Fenwick Tree
Fenwick Tree
Fenwick tree is a data structure effectively supporting \textit{prefix sum} queries.
For a number \textbf{t} denote as \textbf{h(t)} maximal \textbf{k} such that \textbf{t} is divisible by \textbf{2^k}. For example, \textbf{h(24) = 3}, \textbf{h(5) = 0}. Let \textbf{l(t) = 2^\{h(t)\}}, for example, \textbf{l(24) = 8}, \textbf{l(5) = 1}.
Consider array \textbf{a\[1\]}, \textbf{a\[2\]}, ..., \textbf{a\[n\]} of integer numbers. Fenwick tree for this array is the array \textbf{b\[1\]}, \textbf{b\[2\]}, ..., \textbf{b\[n\] }such that
\includegraphics{https://static.e-olymp.com/content/c6/c6e933b903f7e83fe83dc85496e07e2f5d4d9d03.jpg}
.
So
\textbf{b\[1\] = a\[1\]},
\textbf{b\[2\] = a\[1\] + a\[2\]},
\textbf{b\[3\] = a\[3\]},
\textbf{b\[4\] = a\[1\] + a\[2\] + a\[3\] + a\[4\]},
\textbf{b\[5\] = a\[5\]},
\textbf{b\[6\] = a\[5\] + a\[6\]},
...
For example, the Fenwick tree for the array
\textbf{a = (3, -1, 4, 1,-5, 9)}
is the array
\textbf{b = (3, 2, 4, 7,-5, 4)}.
Let us call an array \textit{self-fenwick} if it coincides with its Fenwick tree. For example, the array above is not self-fenwick, but the array \textbf{a = (0,-1, 1, 1, 0, 9)} is self-fenwick.
You are given an array \textbf{a}. You are allowed to change values of some elements without changing their order to get a new array \textbf{a'} which must be self-fenwick. Find the way to do it by changing as few elements as possible.
\InputFile
The first line of the input file contains \textbf{n} --- the number of elements in the array (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}). The second line contains \textbf{n} integer numbers --- the elements of the array. The elements do not exceed \textbf{10^9} by their absolute values.
\OutputFile
Output \textbf{n} numbers --- the elements of the array \textbf{a'}. If there are several solutions, output any one.
Giriş verilənləri #1
6 3 -1 4 1 -5 9
Çıxış verilənləri #1
0 -1 1 1 0 9