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

#pragma GCC optimize("O3")
const ll N=2e6+55;
array<ll,2>aa[N];
ll p[N],s[N],n;

std::vector<int> solve(std::vector<int>a){
    n=a.size();
    ll l=-1,r=n-1,ans=l;
    while(l<=r){
        ll md=(l+r)/2;
        ll klk=(n)/2-(md+1);
        ll sum=((md+1)*(md+2))/2+(n*(n+1))/2-((n-klk)*(n-klk+1))/2;
        //cout<<md<<' '<<sum<<' '<<p[n-1]/2<<endl;
        if(sum*2>=(n*(n+1))/2){
            //cout<<"!"<<md<<endl;
            ans=md;
            l=md+1;
        }else
            r=md-1;
    }
    vector<int>ret;
    for(int i=0;i<=ans;++i)
        ret.push_back(i);
    for(int i=n-1;i>ans;--i)
        ret.push_back(i);
    return ret;
}
