펜윅 트리

시간 제한

3초

메모리 제한

256 MB

문제

펜윅 트리(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].$

예를 들어

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$ 을 넘지 않는다.

출력

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