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

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