#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> solve2(vector<int> vec) {
    vector<int> ans(n);

    int biggest = 0, cnt = 0;
    vector<int> big;

    for(int i = 0; i < n; i++) {
        if(vec[i] > biggest) {
            biggest = vec[i];
            cnt = 1;
        } else if(vec[i] == biggest) {
            cnt++;
        }
    }

    int remaining = (n - cnt) / 2;
    int poz = 0;

    for(int i = 0; i < n; i++) {
        if(vec[i] < biggest) {
            ans[poz] = i;
            poz++;

            if(poz == remaining)
                break;
        }
    }

    for(int i = 0; i < n; i++) {
        if(vec[i] == biggest) {
            ans[poz++] = i;
        }
    }

    int weirdo = n - 1;

    for(int i = n - 1; i >= 0; i--) {
        if(vec[i] < biggest) {
            if(poz <= n - 1)
                ans[poz] = i;
            else
                break;
            poz++;
        }
    }

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