#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
long long seed=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(seed);
vector<int>ans[100000];
long long sum,s;
int n,x;
vector<int> solve(vector<int>a) {
    sum=0;
    s=0;
    n=a.size();
    x=rng()%100000;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(i%2==0){
            if(i==n-1)ans[x].push_back(i);
            else if(a[i]<a[i+1])ans[x].push_back(i);
            else ans[x].push_back(i+1);
            s+=a[ans[x].back()];
        }
        //cout<<s<<" "<<ans.back()<<"!\n";
    }
    //cout<<sum<<" "<<s<<"?\n";
    if(s<=sum/2){
        for(int i=0;i<n;i+=2){
            if(a[i]>a[i+1]){
                ans[x][i/2]=i;
                s+=a[i]-a[i+1];
            }else{
                ans[x][i/2]=i+1;
                s+=a[i+1]-a[i];
            }
            //cout<<ans[i/2]<<" "<<s<<"\n";
            if(s>sum/2){
                swap(ans[x][i/2],ans[x][(n+1)/2-1]);
                break;
            }
        }
    }
    for(int i=0;i<(n+1)/2;i++){
        if(ans[x][i]==n-1&&n%2==1)continue;
        ans[x].push_back((ans[x][i]^1));
    }
    return ans[x];
}
