#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int> a)
{
    vector<pair<int, int>> p;
    for(int i=0; i<a.size(); i++)
    {
        p.push_back({a[i], i});
    }
    sort(p.begin(), p.end());
    int st=0, dr=a.size()-1;
    vector<int> ans(a.size());
    if(a.size()%2==0)
    {
        for(int i=0; i<a.size(); i+=2)
        {
            ans[i]=p[st].second;
            ans[i+1]=p[dr].second;
            st++;
            dr--;
        }
    }
    else
    {
        ans[0]=p[st].second;
        st++;
        for(int i=1; i<a.size(); i+=2)
        {
            ans[i]=p[st].second;
            ans[i+1]=p[dr].second;
            st++;
            dr--;
        }
    }
    return ans;
}