#include "partition.h"
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
std::vector<int> solve(std::vector<int> A)
{
    vector<pair<int,int>> v;
    ll sum = 0;
    for(int i = 0; i < A.size(); i ++)
    {
        sum += A[i];
        v.push_back(make_pair(A[i], i));
    }
    //sort(v.begin(), v.end());
    vector<int> a, b;
    ll s1 = 0, s2 = 0;
    int i = 0;
    if( sum % 2 == 0) sum = sum / 2;
    else sum = (sum / 2) + 1;
    while( s1 < sum && s2 < sum && i < v.size())
    {
        s1 += v[i].first;
        a.push_back(v[i].second);
        if(i + 1 < v.size())
        {
            s2 += v[i + 1].first;
            b.push_back(v[i + 1].second);
        }
        i += 2;
    }
    vector<int> ans;
    if(s1 >= sum)
    {
        for(int i : a) ans.push_back(i);
        for(int i : b) ans.push_back(i);
    }
    else
    {
        for(int i : b) ans.push_back(i);
        for(int i : a) ans.push_back(i);
    }
    return ans;
}
