#include <bits/stdc++.h>
#include "partition.h"

using namespace std;
const int nmax = 2e6;
struct ura
{
    int ord, val;
}v[nmax + 1];
bool cmp(ura a, ura b)
{
    if(a.val < b.val)
        return true;
    if(a.val > b.val)
        return false;
    return true;
}
std::vector<int> solve(std::vector<int> A)
{
    int n = A.size(), i, j;
    vector <int> sol(n);
    long long a = 0, s = 0;
    for(i = 0; i < n; i++)
    {
        s += A[i];
        v[i].ord = i;
        v[i].val = A[i];
    }
    s = (s + 1) / 2;
    sort(v, v + n, cmp);
    for(i = 0; a < s; i++)
    {
        a += v[i].val;
    }
    i--;
    bool ok = 0;
    for(j = n - 1; !ok && j >= 0; j--)
    {
        a += v[j].val;
        while(i >= 0 && a - v[i].val >= s)
        {
            a -= v[i].val;
            i--;
        }
        if(i + 1 + n - j <= (n + 1) / 2)
        {
            ok = 1;
            i += (n + 1) / 2 - (i + 1 + n - j);
        }
    }
    int k, st = 0;
    for(k = 0; k <= i; k++)
        sol[st++] = v[k].ord;
    for(k = n - 1; k > j; k--)
        sol[st++] = v[k].ord;
    for(i++; i <= j; i++)
        sol[st++] = v[i].ord;
    return sol;
}