#include "partition.h"
std::vector<int> solve(std::vector<int> A){
    int v[100001],i=0,n,ls;
    long long s=0,half;
    for(int x:A){
        s+=x;;
        i++;
    }
    n=i;
    half=(s+1)/2;
    long long sp=0,spa=0,beg=0,en=(n+1)/2-1,tip=0;
    ls=n/2;
    if(n%2==0){
        for(i=0;i<ls;i++){
            sp+=A[i];
        }
        for(i;i<n;i++){
            spa=sp;
            sp=sp+A[i]-A[i-ls];
            if(sp>=half && spa<half){
                en=i;
                beg=i-ls+1;
                tip=0;
                break;
            }
            if(sp<half && spa>=half){
                en=i-1;
                beg=i-ls;
                tip=1;
                break;
            }
        }
    }
    else{
        for(i=0;i<ls;i++){
            sp+=A[i];
        }
        for(i;i<n;i++){
            if(sp<half){
                if(i!=ls && sp+A[i-ls-1]>=half){
                    en=i-1;
                    beg=i-ls-1;
                    tip=1;
                    break;
                }
                if(sp+A[i]>=half){
                    en=i;
                    beg=i-ls;
                    tip=0;
                    break;
                }
            }
            sp=sp+A[i]-A[i-ls];
        }
    }
    std::vector<int>ans;
    if(tip==0){
        for(i=beg;i<=en;i++){
            ans.push_back(i);
        }
    }
    else{
        for(i=en;i>=beg;i--){
            ans.push_back(i);
        }
    }
    for(i=0;i<n;i++){
        if(i<beg || i>en){
            ans.push_back(i);
        }
    }
    for(i=0;i<n;i++){
       //std::cout<<ans[i]<<' ';
    }
    //std::cout<<'\n';
    return ans;
}