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

struct ura
{
    int i,val;
}v[2000001];

int cmp (ura a , ura b)
{
    return a.val > b.val;
}
int vc[2000001];

std::vector<int> solve(std::vector<int> A)
{
    int n = A.size();
    long long total = 0;
    int p = 1;
    int subtask2 = 0;
    int subtask3 = 0;
    for (int i = 0; i < n; i++)
    {
        total += A[i];
        v[i + 1].i = i + 1;
        v[i + 1].val = A[i];
    }
    int nr = n / 2;
    std::sort (v + 1 , v + n + 1 , cmp);
    std::vector<int> rez;
    while (nr > 0)
    {
        int sum1 = 0;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            sum1 += v[i].val;
            vc[i] = 1;
            cnt++;
            if (sum1 >= total / 2)
            {
                if (cnt == nr)
                {
                    for (int j = 1; j <= n; j++)
                    {
                        if (vc[j] == 1)
                        {
                            rez.push_back(v[j].i - 1);
                        }
                    }
                    for (int j = 1; j <= n; j++)
                    {
                        if (vc[j] == 0)
                        {
                            rez.push_back(v[j].i - 1);
                        }
                    }
                    return rez;
                    i = n + 1;
                    nr = -1;
                }
                else
                {
                    vc[i]--;
                    sum1 -= v[i].val;
                    cnt--;
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            vc[i] = 0;
        }
        nr--;
    }
}