#include "partition.h"
#include "bits/stdc++.h"
using namespace std;

#define ll long long
const ll INF=1e18;
vector<ll>a;
int N;

ll get(vector<int>res){
      ll sum=0;
      for(ll x:res) sum+=a[x];
      ll cur=0,cnt=0;
      for(ll i=0;i<N;i++){
            cur+=a[res[i]];
            cnt++;
            if(cur>=sum/2ll+(sum&1ll)) break;
      }
      ll c1=cnt;
      ll c2=N-cnt;
      return abs(c1-c2);
}

vector<int>solve(vector<int>A)
{
      int n=A.size();
      if(n%2==0){
            vector<int>v1,v2;
            int turn=1;
            for(int i=0;i<n;i+=2){
                  if((n/2)%2==0&&turn==n/2-1){
                        v1.push_back(i+1);
                        v2.push_back(i);
                        continue;
                  }
                  if((n/2)%2==1&&turn==n/2){
                        v1.push_back(i+1);
                        v2.push_back(i);
                        continue;
                  }
                  if(turn&1){
                        v1.push_back(i);
                        v2.push_back(i+1);
                  }
                  else{
                        v1.push_back(i+1);
                        v2.push_back(i);
                  }
                  turn++;
            }
            vector<int>res;
            for(int x:v1) res.push_back(x);
            for(int x:v2) res.push_back(x);
            return res;
      }
      else{
            vector<int>v1,v2,res;
            int turn=1;
            for(int i=1;i<n;i+=2){
                  if(turn&1){
                        v1.push_back(i);
                        v2.push_back(i+1);
                  }
                  else{
                        v1.push_back(i+1);
                        v2.push_back(i);
                  }
                  turn++;
            }
            v1.push_back(0);
            for(int x:v1) res.push_back(x);
            for(int x:v2) res.push_back(x);
            return res;
      }
}
