#include "partition.h"
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long llong;

const int MAXN = 2e6 + 10;

int n;
int a[MAXN];
llong sum;

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

    sum = 0;

    for(int i = 0; i < n; i++)
    {
        a[i] = A[i];
        sum += a[i];
    }

    vector < pair < int, int > > ord;

    for(int i = 0; i < n; i++)
    {
        ord.push_back({a[i], i});
    }

    sort(ord.begin(), ord.end());

    vector < int > s1;
    vector < int > s2;

    int sz = n / 2;

    for(int i = 0; i < sz - 1; i++)
    {
        s1.push_back(ord[i].second);
    }

    s1.push_back(ord.back().second);

    for(int i = sz - 1; i < n - 1; i++)
    {
        s2.push_back(ord[i].second);
    }

    vector < int > ans;

    for(int idx : s1)
    {
        ans.push_back(idx);
    }
    
    for(int idx : s2)
    {
        ans.push_back(idx);
    }

    return ans;
}
