#include "partition.h"

#include <iostream>
#include <vector>
#include <algorithm>


#define X first
#define Y second
#define control std::cout<<"passed\n";
#define maxn 200005
#define maxlog 21
#define PB push_back



std::vector<int> solve(std::vector<int> a)
{
    /*int sum = 0;
    for(auto& e : a)
        sum += e;

    int n = a.size();

    int ans = 1e9;
    int ret = 0;


    for(int mask = 0; mask < (1 << (n)); mask++)
    {
        int sum1 = 0 , maxx = -1;
        for(int i = 0; i < n; i++)
            if(mask & (1 << i))
                sum1 += a[i] , maxx = std::max(maxx , a[i]);

        int sum2 = sum - sum1;

        if(sum1 < sum2 || ((sum1 - maxx) >= ((sum + 1) / 2)))
            continue;

        int diff = abs(n - __builtin_popcount(mask) * 2);
        if(ans > diff)
        {
            ans = diff;
            ret = mask;
        }
    }
    std::vector <int> rr;
    for(int i = 0; i < n; i++)
        if(ret & (1 << i))
            rr.PB(i);

    std::sort(rr.begin() , rr.end() , [&](int i , int j)
              {
                  return a[i] < a[j];
              });

    for(int i = 0; i < n; i++)
        if(!(ret & (1 << i)))
            rr.PB(i);*/
    /**std::vector <int> ret;
    for(int i = 0; i < a.size(); i++)
        if(i % 2 == 0)
            ret.PB(i / 2);
        else
            ret.PB(a.size() - ((i + 1) / 2));


    if((int)a.size() % 2 == 0)
    {
        //std::cerr << "in" << "\n";
        for(int i = 0; i < a.size(); i += 2)
            std::swap(ret[i] , ret[i + 1]);
    }*/

    std::vector <int> p;
    for(int i = 0; i < a.size(); i++)
        p.PB(i);
    std::sort(p.begin() , p.end() , [&](int i , int j)
              {
                  return a[i] > a[j];
              });

    std::vector <int> ret;
    for(int i = 0; i < a.size(); i++)
        if(i % 2 == 0)
            ret.PB(p[i / 2]);
        else
            ret.PB(p[(int)(a.size()) - ((i + 1) / 2)]);


    return ret;
}
