#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;


int n;

std::vector<int> solve(std::vector<int> A){
    n = A.size();
    long long sum = 0ll;
    for(int i = 0; i < n; ++i){
        sum += A[i];
    }
    //sort(a, a+n);
    int sz = (n+1)/2, idx = 0, gr = sz;
    long long tmp = 0ll;
    for(int i = 0; i < sz; ++i) tmp += A[i];
    sum = (sum+1)/2;
    while(tmp > sum){
        //cout << idx << endl;
        tmp += A[gr] - A[idx];
        idx++;
        gr++;
        if(gr >= n) gr = 0;
        else if(idx >= n){
            idx = 0;
            break;
        }
    }
    while(tmp < sum){
        //cout << idx << endl;
        tmp += A[gr] - A[idx];
        idx++;
        gr++;
        if(gr >= n) gr = 0;
        else if(idx >= n){
            idx = 0;
            break;
        }
    }
    /*for(int i = 0; i < (n+1)/2; ++i){
        tmp += a[i][0];
    }
    for(int i = 1;; ++i){
        if(tmp >= (sum+1)/2) break;
        else{
            tmp += a[n-i][0] - a[(n+1)/2-i][0];
            swap(a[(n+1)/2-i], a[n-i]);
        }
    }*/
    int id = 0;
    vector<int> r(n);
    for(int i = idx;;){
        r[id] = i;
        ++id;
        ++i;
        if(i >= n) i = 0;
        if(id == n) break;
    }
    /*for(int i = idx; i < idx+sz; ++i) r.push_back(a[i][1]);
    for(int i = 0; i < idx; ++i) r.push_back(a[i][1]);
    for(int i = idx+sz; i < n; ++i) r.push_back(a[i][1]);*/
    return r;
}
