#include "partition.h"
#include<algorithm>
using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int terminator = 0;
    int terminator_ind = 0;
    for(int i = 0; i < A.size(); i++) if(A[i] > terminator) {
        terminator = A[i];
        terminator_ind = i;
    }

    int cnt = A.size()/2;
    vector<int> indices;
    int i = 0;
    for(; i < A.size() && cnt; i++) {
        if(A[i] < terminator) {
            indices.push_back(i);
            cnt--;
        }
    }
    indices.push_back(terminator_ind);

    for(; i < A.size(); i++) {
        if(A[i] < terminator) {
            indices.push_back(i);
        }
    }
    return indices;
}
