    #include "partition.h"
    #include<algorithm>
    using namespace std;
    std::vector<int> solve(std::vector<int> a) {
        int n=a.size();
        long long sum=0;
        vector<pair<int,int>> m;
        for(int i=0;i<n;i++) {
            sum+=a[i];
            m.push_back({a[i],i});
        }
        if(sum&1) sum++;
     //   sort(m.begin(),m.end());
        vector<int> v;
        if(n&1)//nechetno
        {
            long cur=0;
            int ind=n/2;
            for(int i=0;i<n;i++){
                cur+=m[i].first;
                v.emplace_back(m[i].second);
                if(cur>=sum/2) {ind=i+1;break;}
                if(i>=ind-1 && cur+m[n-1].first>=sum/2) {ind=i+1;break;}
            }
            v.push_back(m[n-1].second);
            for(int i=ind+1;i<n;i++)v.push_back(m[i-1].second);
        }
        else{
            long cur=0;
            int ind=n/2-1;
            for(int i=0;i<n;i++){
                cur+=m[i].first;
                v.emplace_back(m[i].second);
                if(cur>=sum/2) {ind=i+1;break;}
                if(i>=ind-1 && cur+m[n-1].first>=sum/2) {ind=i+1;break;}
            }
            v.push_back(m[n-1].second);
            for(int i=ind+1;i<n;i++)v.push_back(m[i-1].second);
        }
        return v;
    }
