#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e6+10;
int a[N],b[N];
vector<int>solve(vector<int>A){
    int n=A.size();
    int m1=n/2,m2=n/2;
    if(n%2==1)m2++;
    for(int i=0;i<n/2;i++)a[i]=i;
    for(int i=n/2;i<n;i++)b[i-n/2]=i;
    ll sum1=0,sum2=0;
    for(int i=0;i<m1;i++)sum1+=A[a[i]];
    for(int i=0;i<m2;i++)sum2+=A[b[i]];
    if(sum1<sum2){
        for(int i=0;i<m1+5;i++)swap(a[i],b[i]);
        swap(sum1,sum2);
        swap(m1,m2);
    }
    for(int i=0;i<max(m1,m2);i++){
        if(i==min(m1,m2)&&m1!=m2){
            if(m1>m2){
                sum1-=A[a[m1-1]];
                sum2+=A[a[m1-1]];
                b[m2++]=a[--m1];
            }
            else{
                sum1+=A[b[m2-1]];
                sum2-=A[b[m2-1]];
                a[m1++]=b[--m2];
            }
            break;
        }
        sum1-=A[a[i]];
        sum2-=A[b[i]];
        swap(a[i],b[i]);
        sum1+=A[a[i]];
        sum2+=A[b[i]];
        if(sum1<=sum2){
            swap(b[i],b[m2-1]);
            break;
        }
    }
    vector<int>res;res.reserve(n);
    for(int i=0;i<m2;i++)res.pb(b[i]);
    for(int i=0;i<m1;i++)res.pb(a[i]);
    return res;
}
