#include "partition.h"
#include "bits/stdc++.h"

#define ll long long

using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();

    sort(a.begin(), a.end());

    vector<ll> p(a);

    for (int i = 1; i < n; i++) {
        p[i] += p[i - 1];
    }

    int ans = inf;

    for (int i = 0; i < n; i++) {
        int sum = p[i];

        for (int j = 0; j <= i; j++) {
            int x;

            if (!j) {
                x = a[i];
            }
            else {
                x = a[n - 1];
            }

            if (sum * 2 >= p[n - 1] && (sum - x) * 2 < p[n - 1]) {
                ans = min(ans, abs(i + 1 - (n - i - 1));
            }

            sum -= a[i - j];
            sum += a[n - i - 1];
        }
    }

    return ans;
}
