#include "partition.h"
#include <bits/stdc++.h>

std::vector<int> solve(std::vector<int> A) {

    const int N = A.size();
    double S = 0;

    std::vector<std::pair<int, int>> sorted(N);
    for (int i = 0; i < N; i++) {
        sorted[i].first = A[i];
        sorted[i].second = i;
        S += A[i];
    }

    std::sort(sorted.begin(), sorted.end());

    bool flag = true;
    int first = 0, last = N - 1;
    double sum = 0;

    std::vector<int> answer;

    while (sum < S / (double)2) {
        if (flag) {
            sum += sorted[last].first;
            answer.push_back(sorted[last].second);
            last--;
        } else {
            sum += sorted[first].first;
            answer.push_back(sorted[first].second);
            first++;
        }
        flag = !flag;
    }

    for (int i = first; i <= last; i++) {
        answer.push_back(sorted[i].second);
    }

    return answer;
}
