펜윅 트리

펜윅 트리(Fenwick tree)는 구간 합(prefix sum) 질의를 효율적으로 지원하는 자료구조이다.

양의 정수 $t$에 대해, $t$가 $2^k$로 나누어떨어지는 가장 큰 $k$를 $h(t)$라 하자. 예를 들어 $h(24) = 3$, $h(5) = 0$이다. 그리고 $l(t) = 2^{h(t)}$로 정의하면 $l(24) = 8$, $l(5) = 1$이 된다. 즉, $l(t)$는 $t$에서 가장 낮은 자리에 켜져 있는 비트(lowest set bit)의 값과 같다.

정수 배열 $a[1], a[2], \dots, a[n]$이 주어졌을 때, 이 배열의 펜윅 트리는 다음과 같이 정의되는 배열 $b[1], b[2], \dots, b[n]$이다.

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

예를 들어

$$\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}$$

와 같이 계속된다. 구체적인 예로, $a = (3, -1, 4, 1, -5, 9)$의 펜윅 트리는 $b = (3, 2, 4, 7, -5, 4)$이다.

어떤 배열이 자기 자신의 펜윅 트리와 같을 때, 그 배열을 자기 펜윅(self-fenwick) 배열이라고 부른다. 위 배열은 자기 펜윅 배열이 아니지만, $a = (0, -1, 1, 1, 0, 9)$는 자기 펜윅 배열이다.

배열 $a$가 주어진다. 원소들의 위치와 순서는 그대로 둔 채 일부 원소의 값을 바꾸어, 결과 배열 $a'$가 자기 펜윅 배열이 되도록 만들 수 있다. 이때 바꿔야 하는 원소의 최소 개수를 구하여라.

첫째 줄에 배열의 원소 개수 $n$이 주어진다 ($1 \le n \le 100,000$).

둘째 줄에 배열의 원소인 $n$개의 정수가 주어진다. 각 원소의 절댓값은 $10^9$을 넘지 않는다.

배열이 자기 펜윅 배열이 되도록 하기 위해 바꿔야 하는 원소의 최소 개수를 정수 하나로 출력한다.