#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> solve(std::vector<int> A) {
	
	int n = A.size();
	
	vector <int> a = A;
	
	int sb1 = 0;
	bool sb2, sb3, sb4;
	sb2 = sb3 = sb4 = true;
	
	long long pw2 = 1;
	
	vector <int> answer( n );
	
	map <int, int> mp;
	
	for ( long long i = 0; i < n; i++ ) {
		
		if ( a[i] != pw2 ) {
			sb2 = false;
		}
		
		if ( a[i] != i + 1 ) {
			sb4 = false;
		}
		
		pw2 *= 2;
		
		answer[i] = i;
		
	}
	
	if ( sb4 == true ) {
	
		int l = 0, r = n - 1;
		
		for ( int i = 0; i < n; i++ ) {
			
			if ( i % 2 == 1 ) {
				
				answer[i] = l;
				l++;
				
			} else {
				
				answer[i] = r;
				r--;
				
			}
			
		}
		
		return answer;
	
	} else if ( sb2 == true ) {
		
		for ( int i = 0; i < n / 2 + ( n % 2 ) - 1; i++ ) {
			
			answer[i] = i;
			
		}
		
		answer[n / 2 + ( n % 2 ) - 1] = n - 1;
		
		for ( int i = n / 2 + ( n % 2 ); i < n; i++ ) {
			
			answer[i] = i - 1;
			
		}
		
		return answer;
		
	}
		
	int l = 0, r = n - 1;
		
	for ( int i = 0; i < n; i++ ) {
			
		mp[a[i]]++;
			
		if ( mp[a[i]] % 2 == 1 ) {
				
			answer[l] = i;
				
			l++;
			
		} else {
				
			answer[r] = i;
				
			r--;
				
		}
			
	}
	
	return answer;
	
}
/*
extern vector<int> solve(vector<int> A);
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t ;
    for (int test=1; test<=t; test++) {
        int n;
        cin >> n ;
        vector <int> a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i] ;
        }

        vector <int> ind = solve( a );
        
        for ( int i = 0; i < n; i++ ) {
        	
        	cout << ind[i] << " ";
        	
		}
        
        cout << endl ;
    }
    cout << endl ;
    return 0;
}*/