Code: Rational Bubble Sort

/**
 *    author:  tourist
 *    created: 28.03.2026 08:40:49
 **/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        vector<int64_t> pref(n + 1);
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + a[i];
        }
        if (2 * pref[n] % n == 0) {
            int avg = int(2 * pref[n] / n);
            int ptr = 0;
            while (ptr < n) {
                if (2 * a[ptr] == avg) {
                    ptr += 1;
                } else {
                    if (ptr < n - 1 && a[ptr] + a[ptr + 1] == avg) {
                        ptr += 2;
                    } else {
                        break;
                    }
                }
            }
            if (ptr == n) {
                cout << "Yes" << '\n';
                continue;
            }
        }
        bool found = false;
        for (int i = 1; i < n; i++) {
            int64_t num_l = pref[i];
            int den_l = i;
            int64_t num_r = pref[n] - pref[i];
            int den_r = n - i;
            if (num_l * den_r < num_r * den_l) {
                found = true;
                break;
            }
        }
        cout << (found ? "Yes" : "No") << '\n';
    }
    return 0;
}