#include "partition.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

struct Element
{
    int val;
    int idx;
};

std::vector<Element> a;
std::vector<int> perm;
std::vector<int> permL;
std::vector<int> permR;

std::vector<int> solve(std::vector<int> A)
{
    for(int i = 0 ; i < A.size() ; ++i)
    {
        a.push_back({A[i], i});
    }

    std::sort(a.begin(), a.end(), [&](const Element &left, const Element &right)
    {
        return left.val < right.val;
    });

    int cnt = 0;
    int lPtr = 0, rPtr = a.size() - 1;
    while(true)
    {
        if(lPtr == rPtr)
        {
            permL.push_back(a[lPtr].idx);
            break;
        }

        if(cnt % 2 == 0)
        {
            permL.push_back(a[lPtr].idx);
            permL.push_back(a[rPtr].idx);
        }
        else
        {
            permR.push_back(a[lPtr].idx);
            permR.push_back(a[rPtr].idx);
        }

        if(lPtr + 1 == rPtr)
        {
            break;
        }

        lPtr++;
        rPtr--;
        cnt++;
    }

    for(int x : permL)
    {
        perm.push_back(x);
    }

    for(int x : permR)
    {
        perm.push_back(x);
    }

    return perm;
}
