Submission #67142951

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
*/

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        auto b = a;
        sort(b.begin(), b.end());
        int k = -1;
        for(int i = 0; i < n; i++) {
            if(b[i] == a[0]) {
                k = i;
                break;
            }
        }
        if(a[n - 1] <= 2 * a[0] && n != 1) {
            cout << 2 << '\n';
            continue;
        }
        int ans = 1;
        bool bad = false;
        while(k < n) {
            int j = upper_bound(b.begin(), b.end(), 2 * b[k]) - b.begin();
            j--;
            if(j == k) {
                bad = true;
                break;
            }
            if(b[j] > 2 * b[k]) {
                bad = true;
                break;
            }
            k = j;
            ans++;
            if(b[k] >= a[n - 1]) break;
        }
        cout << (bad ? -1 : ans) << '\n';
    }
}

Submission Info

Judge Result