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

const long long maxa = 3 * 1e7 + 2;

const long long maxn = 2 * 1e6 + 2;
int br[maxa];

vector<int> solve(vector<int> A){
    vector<int> ans;
    int n = A.size();

    /*if(n == 1){
        ans.push_back(0);
    }*/

    bool check = true, check2 = true;

    for(int i = 0 ; i < n ; i ++){
        br[A[i]] ++;
        if(A[i] != i + 1){
            check2 = false;
        }
    }
    for(int i = 0 ; i < n ; i ++){
        if(br[A[i]] % 2 == 1){
             check = false;
        }
    }

    if(check){
        for(int i = 0 ; i < n ; i ++){
            if(br[A[i]] % 2 == 0){
                ans.push_back(i);
            }
            br[A[i]] --;
        }

        for(int i = 0 ; i < n ; i ++){
            if(br[A[i]] % 2 == 1){
                ans.push_back(i);
            }
            br[A[i]] ++;
        }
    }else{

        if(check2){
            if(n % 4 == 0){
                for(int i = 0 ; i < n ; i += 2){
                    if(i == n / 2){
                        i ++;
                    }
                    ans.push_back(i);
                }
                for(int i = 1 ; i < n ; i += 2){
                    if(i == n / 2 + 1){
                        i --;
                    }
                    ans.push_back(i);
                }
            }

            if(n % 4 == 1){
                ans.push_back(0);
                for(int i = 1 ; i < n ; i += 2){
                    if(i == n / 2 + 1){
                        i ++;
                    }
                    ans.push_back(i);
                }
                for(int i = 2 ; i < n ; i += 2){
                    if(i == n / 2 + 2){
                        i --;
                    }
                    ans.push_back(i);
                }
            }

            if(n % 4 == 2){
                ans.push_back(1);
                for(int i = 2 ; i < n ; i += 2){
                    if(i == n / 2 + 1){
                        i ++;
                    }
                    ans.push_back(i);
                }
                for(int i = 3 ; i < n ; i += 2){
                    if(i == n / 2 + 2){
                        i --;
                    }
                    ans.push_back(i);
                }
                ans.push_back(0);
            }

            if(n % 4 == 3){
                ans.push_back(0);
                ans.push_back(1);

                for(int i = 3 ; i < n ; i += 2){
                    if(i == n / 2 + 2){
                        i ++;
                    }
                    ans.push_back(i);
                }
                for(int i = 4 ; i < n ; i += 2){
                    if(i == n / 2 + 3){
                        i --;
                    }
                    ans.push_back(i);
                }

                ans.push_back(2);
            }

        }else{
            for(int i = 0 ; i < n - 1 ; i ++){
                if(i == (n - 1) / 2){
                    ans.push_back(n - 1);
                }
                ans.push_back(i);
            }
        }
    }

    return ans;
}
