#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int N=34e6+1;
vector<int> solve(vector<int> A) {
    vector<int> v;
    v.clear();
    int n=A.size();
    if (n==1) {
        v.push_back(0);
        return v;
    }
    bool bl=true, b[N];
    for (int i=n; i>n/2; i--) {
        if (A[i-1]!=i) {
            bl=false;
            break;
        }else {
            v.push_back(i-1);
            if (i-1!=n-i) v.push_back(n-i);
        }
    }

    if (bl) {
        return v;
    }else {
        v.clear();
        bl=true;
        for (int i=0; i<n; i++) {
            if (A[i]!=(1<<i)) {
                bl=false;
                break;
            }
        }
        if (bl) {
            for (int i=0; i<n; i++) v.push_back(i);
            v[n/2-1]=n-1;
            v[n-1]=n/2-1;
            return v;
        }else {
            for (int i=0; i<N; i++) {
                b[i] = false;
            }
            vector<int> cur1, cur2, v;
            for (int i=0; i<A.size(); i++) {
                if (b[A[i]]) {
                    b[A[i]] = false;
                    cur1.push_back(i);
                }else {
                    b[A[i]] = true;
                    cur2.push_back(i);
                }
            }
            for (auto it : cur2)  v.push_back(it);
            for (auto it: cur1) v.push_back(it);
            return v;
        }
    }

}
