#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

std::vector<int> solve(std::vector<int> A) {
    vector<ll> a;
    for (auto u: A){
        a.push_back(u);
    }
    ll n=A.size();
    if (n==1){
        return {0};
    }
    vector<pair<ll, ll>> d(n/2);
    for (ll i=0; i<n/2; i++){
        d[i]={abs((ll)A[2*i]-(ll)A[2*i+1]), 2*i};
    }
    if (n%2==1){
        d[n/2-1]={abs((ll)A[n-3]+(ll)A[n-2]-(ll)A[n-1]), n-3};
    }
    sort(d.begin(), d.end());
    vector<ll> r1, r2;
    vector<int> r;
    ll x=0, y=0;
    for (auto u: d){
        ll v=u.second;
        if (n%2==1 and v==n-3){
            if ((x<y and (ll)A[n-3]+(ll)A[n-2]<(ll)A[n-1]) or (x>y and (ll)A[n-3]+(ll)A[n-2]>(ll)A[n-1])){
                r1.push_back(n-1);
                r2.push_back(n-2);
                r2.push_back(n-3);
                x+=(ll)A[n-1];
                y+=(ll)A[n-2]+(ll)A[n-3];
            } else {
                r2.push_back(n-1);
                r1.push_back(n-2);
                r1.push_back(n-3);
                y+=(ll)A[n-1];
                x+=(ll)A[n-2]+(ll)A[n-3];
            }
            continue;
        }
        if ((x<y and A[v]<A[v+1]) or (x>y and A[v]>A[v+1])){
            r1.push_back(v+1);
            r2.push_back(v);
            x+=(ll)A[v+1];
            y+=(ll)A[v];
        } else {
            r1.push_back(v);
            r2.push_back(v+1);
            x+=(ll)A[v];
            y+=(ll)A[v+1];
        }
    }
    if (x<y){
        swap(r1, r2);
    }
    for (auto u: r1){
        r.push_back((int)u);
    }
    for (auto u: r2){
        r.push_back((int)u);
    }
    return r;
}