#include <bits/stdc++.h>
#include "partition.h"
#define ll long long
using namespace std;

struct elem{
    int x, id;
    bool operator< (const elem& other) const{
        return x < other.x;
    }
}a[2000005];

ll maxp[2000005], maxpref[2000005];
ll sp[2000005];

vector<int> solve(vector<int> v){
    int n = v.size();
    for(int i = 1; i <= n; i++){
        a[i] = {v[i - 1], i - 1};
    }
    for(int i = 1; i <= n; i++){
        sp[i] = sp[i - 1] + a[i].x;
    }
    maxp[n + 1] = 0;
    for(int i = n; i >= 1; i--){
        maxp[i] = max(maxp[i + 1], (ll)a[i].x);
    }
    for(int i = 1; i <= n; i++){
        maxpref[i] = max(maxpref[i - 1], (ll) a[i].x);
    }
    sp[n + 1] = sp[n];
    int bestpref = 0, bestsuf = -1, best = n + 1, curr;
    for(int i = 0; i <= n; i++){
        if(sp[i] >= sp[n] - sp[i]){
            //iau i ultimul
            if(abs(2 * i - n) < best){
                bestpref = i;
                bestsuf = n + 1;
                best = abs(2 * i - n);
            }
            break;
        }
        if(i == 0){
            int st = i, dr = n + 1;
            while(dr - st > 1){
                int mid = st + dr >> 1;
                if(2 * (sp[i] + sp[n] - sp[mid - 1]) >= sp[n]){
                    st = mid;
                }
                else
                    dr = mid;
            }
            if(2 * (sp[i] + sp[n] - sp[st - 1]) >= sp[n] && 2 * (sp[i] + sp[n] - sp[st - 1] - max(maxp[st], maxpref[i])) < sp[n]){
                if(abs(2 * (i + n - st + 1) - n) < best){
                    bestpref = i;
                    bestsuf = st;
                    best = abs(2 * (i + n - st + 1) - n);
                }
            }
            curr = st;
        }
        else{
            while(curr <= n && 2 * (sp[i] + sp[n] - sp[curr - 1] - max(maxp[curr], maxpref[i])) >= sp[n])
                curr++;
            if(2 * (sp[i] + sp[n] - sp[curr - 1]) >= sp[n] && 2 * (sp[i] + sp[n] - sp[curr - 1] - max(maxp[curr], maxpref[i])) < sp[n]){
                if(abs(2 * (i + n - curr + 1) - n) < best){
                    bestpref = i;
                    bestsuf = curr;
                    best = abs(2 * (i + n - curr + 1) - n);
                }
            }
        }
    }
    vector<int> ans;
    for(int i = 1; i <= bestpref; i++){
        ans.push_back(a[i].id);
    }
    for(int j = bestsuf; j <= n; j++){
        ans.push_back(a[j].id);
    }
    for(int i = bestpref + 1; i <= bestsuf - 1; i++){
        ans.push_back(a[i].id);
    }
    return ans;
}
