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

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    vector<int> ans(n);
    pair<int,int> big = {-1,-1};
    pair<int,int> sm = {INT_MAX,-1};
    int t = 0;
    for(int i = 0; i < n; i++) {
        big = max(big,{a[i],i});
        sm = min(sm,{a[i],i});
    }
    if(sm.second == big.second) {
        for(int i = 0; i < n; i++) {
            ans[i] = i;
        }
        return ans;
    }
    if(n%2) {
        int sb = 0;
        int p = 0;
        while(p < n-1) {
            int x = p,y = p+1;
            if(x == big.second) {
                x++;
                y++;
            }
            else if(y == big.second) {
                y++;
            }
            if(y > n-1) {
                break;
            }
            int dif = a[y]-a[x];
            if((dif < 0 && sb > 0) || (dif > 0 && sb < 0)) {
                sb+=dif;
                ans[t] = x;
            }
            else {
                sb-=dif;
                ans[t] = y;
            }
            t++;
            p = y+1;
        }
        ans[t] = big.second;
        t++;
    }
    else {
        int wut[n-2];
        int w = 0;
        for(int i = 0; i < n; i++) {
            if(i != sm.second && i != big.second) {
                wut[w] = i;
                w++;
            }
        }
        int sb = 0;
        for(int i = 0; i+1 < n-2; i+=2) {
            int x = wut[i],y = wut[i+1];
            int dif = a[y]-a[x];
            if((dif < 0 && sb > 0) || (dif > 0 && sb < 0)) {
                sb+=dif;
                ans[t] = x;
            }
            else {
                sb-=dif;
                ans[t] = y;
            }
            t++;
        }
        ans[t] = big.second;
        t++;
    }
    vector<bool> yo(n,true);
    for(int v: ans) {
        yo[v] = false;
    }
    for(int i = 0; i < n; i++) {
        if(yo[i]) {
            ans[t] = i;
            t++;
        }
    }
    return ans;
}
