#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>ans;
long long sum=0,s;
int n;
vector<int> solve(vector<int>a) {
    sum=0;
    s=0;
    ans.clear();
    n=a.size();
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(i%2==0){
            if(i==n-1)ans.push_back(i);
            else if(a[i]<a[i+1])ans.push_back(i);
            else ans.push_back(i+1);
            s+=a[ans.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[i/2]=i;
                s+=a[i]-a[i+1];
            }else{
                ans[i/2]=i+1;
                s+=a[i+1]-a[i];
            }
            //cout<<ans[i/2]<<" "<<s<<"\n";
            if(s>sum/2){
                swap(ans[i/2],ans[(n+1)/2-1]);
                break;
            }
        }
    }
    for(int i=0;i<(n+1)/2;i++){
        if(ans[i]==n-1&&n%2==1)continue;
        ans.push_back((ans[i]^1));
    }
    return ans;
}
