#include<bits/stdc++.h>
#include "partition.h"
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int ind,st;
};
bool cmp(cell a1,cell a2)
{
    return a1.st<a2.st;
}
int t,n;
long long int p[2000005],la;
cell a[2000005];
vector<int> solve(vector<int> A)
{
    vector<int>otg;
    n=A.size();
    long long int sum=0;
    p[n+1]=0;
    la=0;
    for(int i=n; i>=1; i--)
    {
        a[i].st=A[i-1];
        a[i].ind=i;
        sum+=a[i].st;
        if(a[i].st==i)la++;
    }
    if(la!=n)
    {
        sort(a+1,a+n+1,cmp);
    }
    for(int i=n;i>=1;i--)
    {
        p[i]=p[i+1]+a[i].st;
    }
    /*for(int i=1;i<=n;i++)
    {
        cout<<p[i]<<" ";
    }*/
    long long int st=0,br=(n+1)/2,to=1,gg=sum/2+sum%2;
    while(br)
    {
        //cout<<st<<" "<<n-br+2<<" "<<br<<" "<<a[to].st<<endl;
        if(st+p[n-br+2]+a[to].st<gg)break;
        otg.push_back(a[to].ind-1);
        st+=a[to].st;
        br--;
        to++;
    }
    //cout<<endl;
    //cout<<br<<endl;
    int cur=n;
    while(br)
    {
        otg.push_back(a[cur].ind-1);
        cur--;
        br--;
    }
    for(int i=to;i<=cur;i++)
    {
        otg.push_back(a[i].ind-1);
    }
    return otg;
}
