Fenwick Tree

A Fenwick tree is a data structure that efficiently supports prefix-sum queries.

For a positive integer $t$, let $h(t)$ be the largest $k$ such that $t$ is divisible by $2^k$. For example, $h(24) = 3$ and $h(5) = 0$. Let $l(t) = 2^{h(t)}$, so $l(24) = 8$ and $l(5) = 1$. Equivalently, $l(t)$ is the value of the lowest set bit of $t$.

Given an array $a[1], a[2], \dots, a[n]$ of integers, its Fenwick tree is the array $b[1], b[2], \dots, b[n]$ defined by

$$b[i] = \sum_{j=i-l(i)+1}^{i} a[j].$$

For instance,

$$\begin{aligned} 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], \end{aligned}$$

and so on. As a concrete example, the Fenwick tree of $a = (3, -1, 4, 1, -5, 9)$ is $b = (3, 2, 4, 7, -5, 4)$.

Call an array self-fenwick if it is equal to its own Fenwick tree. The array above is not self-fenwick, but $a = (0, -1, 1, 1, 0, 9)$ is.

You are given an array $a$. You may change the value of any element (their positions and order stay fixed) so that the resulting array $a'$ becomes self-fenwick. Determine the minimum number of elements that must be changed.

The first line contains a single integer $n$ — the number of elements in the array ($1 \le n \le 100,000$).

The second line contains $n$ integers — the elements of the array. Each element's absolute value does not exceed $10^9$.

Print a single integer — the minimum number of elements of $a$ that must be changed so that the array becomes self-fenwick.