#include <bits/stdc++.h>
#include "partition.h"
#define endl '\n'

using namespace std;

const int MAXN = 2 * 1e6;

int n;
vector<int>otg;
pair<int,int>a[MAXN + 5];


std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    otg.clear();

    for(int i = 0; i < A.size(); i++)
    {
        a[i] = {A[i], i};
    }

    sort(a, a + n);

    int mid = 0;
    if(n % 2 == 0)mid = n / 2 - 1;
    else mid = n / 2;

    for(int i = 0; i < mid; i++)
    {
        otg.push_back(a[i].second);
    }
    otg.push_back(a[n - 1].second);

    for(int i = mid; i < n - 1; i++)
    {
        otg.push_back(a[i].second);
    }

    return otg;
}
