#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
//vector < pair < int, int > > g;
long long total = 0;
int n, used[maxn];

long long psum[maxn];
long long get(int l, int r)
{
    if(l > r)return 0;
    long long ans = psum[r];
    if(l > 0)ans -= psum[l-1];
    return ans;
}
std::vector<int> solve(std::vector<int> A)
{

    n = A.size();

    vector < pair < long long, int > > g;
    for (int i = 0; i < n; ++ i)
    {
        g.pb(make_pair(A[i], i));
    }
    sort(g.begin(), g.end());
    g.pb(make_pair(0, n));
    for (int i = 0; i < n; ++ i)
    {
        psum[i] = psum[i-1] + g[i].first;
    }
    vector < int > res;
    total = 0;
    for (int i = 0; i < n; ++ i)
        total += A[i];

    int mindif = n+1;
    res.pb(0);

    long long pretook = 0;
    int last = 0;
    int pp = 0;
    int ss = 0;
    int j = 0;
    for (int takepref = 0; takepref <= 0; ++ takepref)
    {
        if(mindif == n%2)break;
        long long took = get(0, takepref - 1);
        if(pretook * 2 >= total)break;
        int lt = takepref, rt = n-1, mid, ans = n; /// nai poslednoto koeto da napravi >= total
        while(lt <= rt)
        {
            mid = (lt + rt)/2;
            if((took + get(mid, n-1))* 2 >= total)
            {
                ans = mid;
                lt = mid + 1;
            }
            else rt = mid - 1;
        }
        if((get(0, takepref-1) + get(ans, n-1)) * 2 >= total)
        {
            int cntis = takepref + max(0, n - 1 - ans + 1);
            int cntisnt = n - cntis;
            if(mindif > abs(cntis - cntisnt))
            {
                mindif = abs(cntis - cntisnt);
                pp = takepref;
                ss = ans;

            }
        }
       j = ans;
    }
    int ans = j;
  //  cout << mindif << endl;
    for (int takepref = 1; takepref < n; ++ takepref)
    {
        if(pretook * 2 >= total)break;
        if(mindif == n%2)break;
         long long took = get(0, takepref - 1);

        while( ans + 1 < n && ( get(ans + 1, n - 1) + took) * 2 <= total)
        {
           // cout << ans << endl;
            ans ++;
        }

        if((get(0, takepref-1) + get(ans, n-1)) * 2 >= total)
        {
            int cntis = takepref + max(0, n - 1 - ans + 1);
            int cntisnt = n - cntis;
            if(mindif > abs(cntis - cntisnt))
            {
                 mindif = abs(cntis - cntisnt);
                pp = takepref;
                ss = ans;
            }
        }
        pretook = took;
    }
    vector < int > curr;
                for (int i = 0; i < pp; ++ i)
                    curr.pb(g[i].second);
                for (int i = ss; i < n; ++ i)
                    curr.pb(g[i].second);
                for (int i = pp; i < ss; ++ i)
                    curr.pb(g[i].second);
                res = curr;

  //  cout << mindif << endl;
    return res;
}
