#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
long long s=0,sum=0,mn=1e18;
vector <pair <int,int>> a;
pair <int,int> x;
vector<int> solve(vector<int> A)
{
    mn=1e18;
    s=0;
    sum=0;
    int n=A.size();
    for(int i=0;i<n;i++)
    {
        s+=A[i];
        a.push_back({A[i],i});
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++)
    {
        sum=0;
        for(int j=i;j<n;j++)
        {
            sum+=a[j].first;
            if(sum>=s/2+s%2)
            {
                if(mn>abs((j-i+1)-(n-(j-i+1))))
                {
                    mn=abs((j-i+1)-(n-(j-i+1)));
                    x={i,j};
                }
                break;
            }
        }
    }
    //cout<<mn<<" "<<x.first<<" "<<x.second<<" "<<s<<" "<<s/2+s%2<<endl;
    vector <int> ans;
    for(int i=x.first;i<=x.second;i++)ans.push_back(a[i].second);
    for(int i=0;i<x.first;i++)ans.push_back(a[i].second);
    for(int i=x.second+1;i<n;i++)ans.push_back(a[i].second);
    return ans;
}
