#include "partition.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

using ll = long long;
std::vector<int> solve(vector<int>v) {
    int n = v.size();
    auto ol = v;
    for(int k = n/2-1; k <= (n+1)/2-1; k++)
    {
        ll sum = 0,idm = 0;
        vector<int> res(n);
        int sz = 0;
        for(int i = 0; i < n ;i++)
        {
            if(v[i]>v[idm])idm = i;
            sum+=v[i];
        }
        int mx = v[idm];
        v.erase(v.begin()+idm);
        vector<int> vis(n,0);
        if(n==1)
        {
            return {0};
        }
        n--;
        ll st = (sum+1)/2;
        ll ini = 0;
        for(int i = 0; i < k; i++)
            ini+=v[i];
        int i = 0;
        for(;i < n && (ini>=st||ini<st-mx); i++)
            ini-=v[i]-v[(i+k)%n];
        
        for(int j = i,cnt = 0;j != (i+k)%n;j=(j+1)%n,cnt++)
        {
            res[sz++]=j+(j>=idm);
            vis[j+(j>=idm)] = 1;
        }
        n++;

        res[sz++]=idm;
        vis[idm] = 1;
        

        for(int cnt = 0; cnt<n;)
        {
            while(cnt<n&&vis[cnt])cnt++;
            if(cnt==n)break;
            vis[cnt] = 1;
            res[sz++]=cnt;
        }
        if(ini<st&&ini+mx>=st)
        return res;
        v = ol;
    }
    assert(0);
    return {0};
}