#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#pragma GCC optimize("O3")

const int N = 2100000;
const int X = 1100;

array<int, 2> B[N];
vector<int> C;
ll pref[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> solve(vector<int> A) {
    int n = A.size();
    for (int i = 0; i < n; i++)
        B[i] = {A[i], i};
    int L = 0, R = 0;
    ll S = accumulate(begin(A), end(A), 0ll), cur = 0;
    while (R < n && cur + B[R][0] <= S / 2) {
        cur += B[R][0];
        R++;
    }
    L = n - R;
    if (cur != S / 2)
        L--;
    if (L > R) {
        reverse(B, B + n);
        swap(L, R);
    }
    for (int i = 0; i < n; i++)
        pref[i] = (i == 0 ? 0 : pref[i - 1]) + B[i][0];
    auto cnt = [&](int k) -> int {
        auto get = [&](int i) -> ll {
            if (i < k) return pref[i];
            if (i < k + n - R) return pref[i - k + R] - (R == 0 ? 0 : pref[R - 1]) + pref[k - 1];
            return pref[n - 1] - (R == 0 ? 0 : pref[R - 1]) + pref[i - n + R];
        };
        int l = -1, r = n;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (get(m) <= S / 2) l = m;
            else r = m;
        }
        return r;
    };
    int v = n / 2;
    v = max(v, L);
    v = min(v, R);
    int l = 0, r = R + 1;
    while (r - l > 1) {
        int k = (l + r) / 2;
        if (cnt(k) <= v) l = k;
        else r = k;
    }
    int k = l;
    C.resize(n);
    for (int i = 0; i < k; i++)
        C[n - 1 - i] = B[i][1];
    for (int i = R; i < n; i++)
        C[n - 1 - i + R - k] = B[i][1];
    for (int i = k; i < R; i++)
        C[n - 1 - i - n + R] = B[i][1];
    return C;
}




















#ifdef LOCAL

extern vector<int> solve(vector<int> A);
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t ;
    for (int test=1; test<=t; test++) {
        int n;
        cin >> n ;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
            a[i] = rng() % (int)(1e9);
        }
        auto beg = chrono::steady_clock::now().time_since_epoch().count();
        vector<int> c = solve(a);
        cout << c.size() << endl;
        auto nd = chrono::steady_clock::now().time_since_epoch().count();
        cout << fixed << setprecision(4) << (nd - beg) / (1e9) << endl;
    }
    cout << endl ;
    return 0;
}

#endif // LOCAL
