Prairie Partition
Contest: VK Cup 2017 - Round 3
Difficulty rating: 2200
Tags: binary search, constructive algorithms, greedy, math

It can be shown that any positive integer x can be uniquely represented as x = 1 + 2 + 4 + ... + 2k - 1 + r, where k and r are integers, k ≥ 0, 0 < r ≤ 2k. Let's call that representation prairie partition of x.

For example, the prairie partitions of 12, 17, 7 and 1 are:

12 = 1 + 2 + 4 + 5,17 = 1 + 2 + 4 + 8 + 2,7 = 1 + 2 + 4,1 = 1.

Alice took a sequence of positive integers (possibly with repeating elements), replaced every element with the sequence of summands in its prairie partition, arranged the resulting numbers in non-decreasing order and gave them to Borys. Now Borys wonders how many elements Alice's original sequence could contain. Find all possible options!

Input format:
The first line contains a single integer n (1 ≤ n ≤ 105) — the number of numbers given from Alice to Borys.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1012; a1 ≤ a2 ≤ ... ≤ an) — the numbers given from Alice to Borys.

Output format:
Output, in increasing order, all possible values of m such that there exists a sequence of positive integers of length m such that if you replace every element with the summands in its prairie partition and arrange the resulting numbers in non-decreasing order, you will get the sequence given in the input.

If there are no such values of m, output a single integer -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, Alice could get the input sequence from [6, 20] as the original sequence.

In the second example, Alice's original sequence could be either [4, 5] or [3, 3, 3].

Example input:
8
1 1 2 2 3 4 5 8

Example output:
2

Example input:
6
1 1 1 2 2 2

Example output:
2 3

Editorial:
This kind of partition sometimes shows up in solutions to knapsack problems with multiple items of the same type.
Let's say we want to check if the answer can be m. That means we have to construct m chains of powers of 2 like 1, 2, 4, ..., 2k - 1 (possibly with different values of k), and then assign at most one of the remaining elements to each chain so that the element doesn't exceed double the largest power of 2 in its assigned chain. If we can assign all the elements successfully, m is one possible answer.
It can be proved that the chains can be constructed greedily one by one, with each chain as long as possible. Let's denote the number of occurrences of integer x in the input by c(x). Then, the number of chains where integer 2k can be used is restricted by bound(2k) = min(c(20), c(21), ..., c(2k)). If we construct the chains greedily, then it's easy to see that the first bound(2k) chains will use 2k. And if we use as many occurrences of powers of 2 as possible, that's better both because we are left with less elements to be assigned to the chains and because the largest powers of 2 in the chains are higher, thus more elements can be assigned to the chains.
Having m chains constructed, how do we quickly check if we can assign the remaining elements to these chains? This can also be done greedily. If we can't assign the largest of the remaining elements to the longest chain, then we can't assign this element to any chain, so there's no possible assignment. Otherwise, remove the largest element and the longest chain from consideration, and repeat the process until we either assign all the elements or run into a failure situation described above. Why is greedy correct? Consider a valid assignment where the largest element E is assigned to some chain c, and some element e is assigned to the longest chain C. If E ≠ e and C ≠ c, it can be seen that we can as well reassign E to C and e to c to get another valid assignment. Thus, if there exists a valid assignment, there also exists one with E assigned to C.
Implemented straightforwardly, this solution works in O(n2). In fact, both factors of n can be optimized.
First, it can be seen that if m is one possible answer but there is at least element equal to 1 not yet involved in any chains, then m + 1 is another possible answer, since when we construct the m + 1-th chain we only make the situation better — we won't have to assigned the elements of this chain to other chains, and we'll have another chain which can be used for assignment too. Therefore, we can perform a binary search on the smallest possible value of m, thus having to do $${\mathcal {O}}(\log n)$$ assignments instead of O(n).
Second, let a be the largest of the input integers. All elements of the input sequence can be distributed into $$2 \log a$$ groups: powers of 2, and integers between consecutive powers of 2. The integers in the groups are effectively indistinguishable from our point of view, which allows us to do the assignment part in $${\mathcal{O}}(\log a)$$.
Applying any of these two optimizations was enough to solve the problem.