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

const long long maxn=1e6+10;
//unordered_map<int,int> cnt1,cnt2;
vector<int> ans;
vector<pair<int,int>> b;
bitset<maxn> visited,clean;
int st[maxn];

vector<int> solve(vector<int> a){
    int n=a.size(),sum1=0,sum2=0,ind1,ind2;
    ans.clear();
    visited=clean;
    ans.assign(n,0);
    int k=1;
    for(int i=1;i<15;i++){
        st[k]=true;
        k*=2;
    }
    if(n%2==0){
        ind1=0;
        ind2=n/2;
        for(int i=0;i<n/2;i++){
            //cout<< sum1 << " " << sum2 << " :: " <<endl;
            if(i==n/2-1 && !st[n]){
                //cout<< "YES";
                if(ind1<n) ans[ind1]=i+1;
                if(ind2<n) ans[ind2]=i;
                break;
            }

            if(!(i%2)){
                if(ind1<n) ans[ind1]=i;
                ind1++;
                if(ind1<n) ans[ind1]=n-i-1;
                sum1+=(i+1);
                sum1+=(n-i);
                ind1++;
            }else{
                //cout<< i << " " << n-i-1 << endl;
                if(ind2<n) ans[ind2]=i;
                ind2++;
                if(ind2<n) ans[ind2]=n-i-1;
                sum2+=(i+1);
                sum2+=(n-i);
                ind2++;
            }
        }
    }else{
        int b1=n-2,b2=n-1;
        ind1=0;
        ind2=n/2+1;
        for(int i=0;i<=n/2;i++){
            //cout<< sum1 << " " << sum2 << " :: " <<  endl;
            if(!(i%2)){
                //cout<< i << " " << b1 << endl;
                if(!visited[i]){
                    if(ind1<n) ans[ind1]=i;
                    sum1+=i+1;
                    ind1++;
                    visited[i]=true;
                }

                if(!visited[b1]){
                    if(ind1<n) ans[ind1]=b1;
                    sum1+=(b1+1);
                    ind1++;
                    visited[b1]=true;
                    b1-=2;
                }
            }else{
                //cout<< i << " " << b2 << endl;
                if(!visited[i]){
                    if(ind2<n) ans[ind2]=i;
                    sum2+=i+1;
                    ind2++;
                    visited[i]=true;
                }

                if(!visited[b2]){
                    if(ind2<n) ans[ind2]=b2;
                    sum2+=(b2+1);
                    ind2++;
                    visited[b2]=true;
                    b2-=2;
                }
            }
        }
    }

    return ans;
}

/*

1
12
5 5 6 3 5 6 5 1 3 1 4 4


6
7
1 2 3 4 5 6 7
6
1 2 3 4 5 6
4
1 2 3 4
3
1 2 3
8
1 2 3 4 5 6 7 8
9
1 2 3 4 5 6 7 8 9

*/
