#include "partition.h"
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

std::vector<int> solve(std::vector<int> A)
{
    int n = A.size();
    vector<pair<long long,int> >v;
    for(int i = 0; i < n; i++) v.push_back({A[i],i});
    sort(v.begin(),v.end());

    int p1 = 0, p2 = n-1;

    vector<int>v1,v2;
    long long s1 = 0, s2 = 0;
    for(int q = 0; q < n; q++)
    {
        if(q % 2 == 0)
        {
            if(s1 + v[p1].first >= s2)
            {
                s1 += v[p1].first;
                v1.push_back(v[p1].second);
                p1++;
            }
            else
            {
                s1 += v[p2].first;
                v1.push_back(v[p2].second);
                p2--;
            }
        }
        else
        {
            if(s2 + v[p1].first >= s2)
            {
                s2 += v[p1].first;
                v2.push_back(v[p1].second);
                p1++;
            }
            else
            {
                s2 += v[p2].first;
                v2.push_back(v[p2].second);
                p2--;
            }
        }
    }
    for(int x : v2) v1.push_back(x);
    return v1;
}
