#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> solve1(vector<int> vec) {
    unordered_map<int, int> ump;
    vector<int> ans(n);
    int poz1 = 0, poz2 = n - 1;

    for(int i = 0; i < n; i++) {
        if(ump[vec[i]] % 2 == 0) {
            ans[poz1++] = i;
        } else {
            ans[poz2--] = i;
        }

        ump[vec[i]]++;
    }

    return ans;
}
vector<int> solve2(vector<int> vec) {
    unordered_map<int, int> ump;
    vector<int> ans(n), positions;
    vector<bool> used(n);
    int poz1 = 0, poz2 = n - 1, biggest = 0, pairs = 0;

    for(int i = 0; i < n; i++) {
        if(ump[vec[i]] == 0) {
            ump[vec[i]] = i;
        } else {
            int lastapp = ump[vec[i]];
            ans[poz1++] = lastapp;
            ans[poz2--] = i;
            pairs++;
            used[lastapp] = used[i] = 1;
            ump[vec[i]] = 0;
        }
    }

    int pozbig = 0;

    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            positions.push_back(i);

            if(biggest < vec[i]) {
                biggest = vec[i];
                pozbig = i;
            }
        }
    }

    int remaining = positions.size();

    if(!remaining)
        return ans;

    if(remaining % 2 == 0) {
        int i;

        int pozpos=0;

        for(i = 0; i < remaining / 2 - 1; i++){
            if(positions[pozpos]==pozbig){
                pozpos++;
            }
            ans[i + pairs] = positions[pozpos++];
        }

        ans[i+pairs] = pozbig;
        i++;

        for(; i < remaining; i++)
            ans[i+pairs] = positions[pozpos++];
    } else {
        int i;

        int pozpos=0;

        for(i = 0; i < remaining / 2; i++){
            if(positions[pozpos]==pozbig){
                pozpos++;
            }
            ans[i + pairs] = positions[pozpos++];
        }

        ans[i+pairs] = pozbig;
        i++;

        for(; i < remaining; i++)
            ans[i+pairs] = positions[pozpos++];
    }

    return ans;
}
vector<int> solve6sau2(vector<int> vec) {
    vector<int> ans(n);

    int minn = 500, sol = 0, special = 0, onessol = 0;
    long long sum = 0;

    for(int i : vec)
        sum = sum + 2 * i;

    for(int mask = 0; mask < (1 << n); mask++) {
        long long localsum = 0;
        int minim = 2e9, unu = 0, zero = n;

        for(int bit = 0; bit < n; bit++) {
            if((1 << bit)&mask) {
                unu++;
                zero--;

                localsum = localsum + 2 * vec[bit];
                minim = min(minim, vec[bit]);
            }
        }

        if(localsum >= sum / 2) {
            for(int bit = 0; bit < n; bit++) {
                if((1 << bit)&mask) {
                    if(localsum - vec[bit] < sum / 2) {
                        if(minn > abs(unu - zero)) {
                            minn = abs(unu - zero);
                            sol = mask;
                            special = bit;
                            onessol = unu;
                        }
                    }
                }
            }
        }
    }

    int poz = 0, last = n - 1;

    ans[onessol - 1] = special;

    for(int i = 0; i < n; i++) {
        if(i == special)
            continue;

        if((1 << i)&sol)
            ans[poz++] = i;
        else
            ans[last--] = i;
    }

    return ans;
}
vector<int> solve4(vector<int> vec) {
    vector<int> ans(n + 1, 0);

    int poz = 0;

    for(int i = 0; i < n; i += 2) {
        ans[i] = n - poz - 1;
        ans[i + 1] = poz;
        poz++;
    }

    ans.pop_back();

    return ans;
}
vector<int> solve5(vector<int> vec) {
    vector<int> seven(n);
    vector<int> ans(n);

    long long sum = 0;

    for(int i : vec)
        sum += 2ll * i;

    for(int i = 0; i < n; i++)
        seven[i] = i;

    int prod = 1;

    for(int i = 2; i <= n; i++)
        prod *= i;

    int minn = 10;

    for(int i = 0; i < prod / 3; i++) {
//        if(i < 10) {
//            for(int dick : seven)
//                cout << dick << " ";
//
//            cout << "\n";
//        }

        long long localsum = 0;
        int last = 0;

        for(int j = 0; j < n; j++) {
            localsum += 2ll * vec[seven[j]];

            if(localsum >= sum / 2) {
                last = j;
                break;
            }
        }

        int dif = max((last + 1) - (n - 1 - last), (n - 1 - last) - (last + 1));

//        cout << i << " " << dif << "\n";

        if(dif < minn) {
            ans = seven;
            minn = dif;
        }

        if(dif == 0)
            break;

        next_permutation(seven.begin(), seven.end());
    }

    return ans;
}
std::vector<int> solve(std::vector<int> A) {
    n = A.size();
    vector<int> ans(n);
    ans = solve2(A);
    return ans;
}
