Codeforces Round 1130 (Div. 1 + Div. 2)

Contest is running 01:20:13

C. Paper Planes

time limit per test 2 seconds memory limit per test 256 megabytes input / output standard

Monocarp has folded n paper planes. The i-th of them flies exactly ai meters.

He is going to launch all n planes from the roof, one after another, in any order he likes. A launch is spectacular if the plane lands strictly farther than every plane launched before it. In particular, the first launch is always spectacular.

Before the launches, Monocarp may refold planes. To refold a plane with range x ≥ 2, he folds it once more, and its range becomes ⌊x / 2⌋. A plane can be refolded any number of times.

What is the maximum number of spectacular launches Monocarp can get?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 104). The description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2·105) — the number of planes.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109) — the ranges of the planes.

It is guaranteed that the sum of n over all test cases does not exceed 2·105.

Output

For each test case, print a single integer — the maximum number of spectacular launches.

Examples

Input 
352 2 2 5 943 3 3 367 7 6 6 2 2
Output 
425
Input 
231000000000 1000000000 100000000011
Output 
31

Note

In the first test case, Monocarp can refold one of the planes with range 2. The ranges become [2, 1, 2, 5, 9], and if he launches the planes in the order 1, 2, 5, 9, 2, the first four launches are spectacular. Three planes of range 2 can only end up with ranges 2 and 1, so five spectacular launches are impossible.

In the second test case, every range can only become 3 or 1, so the answer is 2.

« B. Coin TowersD. Interactive Lighthouse »
Submit
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) cin >> x;
        sort(a.rbegin(), a.rend());

        set<int> used;
        int ans = 0;
        for (int x : a) {
            while (x > 0 && used.count(x)) x /= 2;
            if (!used.count(x)) {
                used.insert(x);
                ans++;
            }
        }
        cout << ans << '\n';
    }
}

My submissions All »

18:24CTime limit exceeded on pretest 32000 ms
17:58BPretests passed62 ms
17:41APretests passed15 ms

Jury announcements

Problem E: it is guaranteed that the given graph is connected.
Problem C: a plane with range 1 cannot be refolded. The statement requires x ≥ 2.