Merge to Minimize Cow Stalls

Farmer John's farm originally had n cow stalls. The i-th stall contains a_i cows. You are allowed to perform a series of merge operations. In each merge operation, you choose two distinct stalls i and j such that a_i \ge a_j. Then, you remove exactly a_j cows from stall i and add them into stall j (i.e. update: a_i = a_i - a_j and a_j = 2a_j). If after the merge a_i = 0, stall i is considered merged and will not participate in further operations.

Notice that if you merge two stalls with equal numbers of cows, one stall will vanish (since a_i - a_j = 0 when a_i = a_j). Such merges decrease the total number of stalls currently holding cows. Merging stalls with unequal counts, while allowed, does not reduce the number of stalls.

Your task is to determine the minimum possible number of non‐merged stalls (i.e. stalls with cows) that can remain after performing an optimal sequence of merge operations. You may perform the operations in any order, and you have a time limit of 1 second.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of cow stalls.

The second line contains n space‐separated positive integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹), where a_i denotes the number of cows in the i-th stall.

outputFormat

Output a single integer – the minimum number of stalls that can remain (i.e. stalls with a positive number of cows) after performing an optimal sequence of merge operations.

sample

2
5 5

1