#include "partition.h"
#include <algorithm>

// std::vector<int> solve(std::vector<int> A) {
//     std::vector <std::pair <int, int>> B;
//     for (int i = 0; i < A.size(); i++) {
//         B.push_back({ A[i], i });
//     }
//     std::sort(B.begin(), B.end());
//     std::vector <int> res;
//     for (int i = 0; i < B.size(); i += 2) {
//         res.push_back(B[i].second);
//     }
//     for (int i = 1; i < B.size(); i += 2) {
//         res.push_back(B[i].second);
//     }

//     return res;
// }

// std::vector<int> solve(std::vector<int> A) {
//     std::vector <std::pair <int, int>> B;
//     for (int i = 0; i < A.size(); i++) {
//         B.push_back({ A[i], i });
//     }
//     std::sort(B.begin(), B.end());
//     std::vector <int> res;
//     for (int i = B.size() - 1; i >= 0; i--) {
//     // for (int i = 0; i < B.size(); i++) {
//         res.push_back(B[i].second);
//     }

//     return res;
// }

// std::vector<int> solve(std::vector<int> A) {
//     std::vector <int> res;
//     for (int i = A.size() - 1; i >= 0; i--) {
//         res.push_back(i);
//     }

//     return res;
// }

std::vector<int> solve(std::vector<int> A) {
    std::vector <int> res;
    if (A.size() % 4 == 0) {
        for (int i = 0; i < (A.size()/2); i++) {
            res.push_back(i);
            res.push_back(A.size() - 1 - i);
        }
    } else if (A.size() % 4 == 1) {
        int h = A.size() / 4;
        res.push_back(h);
        for (int i = 0; i < (A.size()/2); i++) {
            if (i == h) continue;
            res.push_back(i);
            res.push_back(A.size() - 1 - i);
        }
        if (A.size() > 1) {
            res.push_back(A.size() - 1 - h);
            res.push_back(A.size() / 2);
        }
    } else if (A.size() % 4 == 2) {
        int h = A.size() / 2;
        res.push_back(h);
        for (int i = 0; i < (A.size()/2-1); i++) {
            if (i == h) continue;
            res.push_back(i);
            res.push_back(A.size() - 1 - i);
        }
        res.push_back(A.size() - 1 - h);
    } else if (A.size() % 4 == 3) {
        int h  = (A.size()+1) / 4 * 3 - 1;
        res.push_back(h);
        for (int i = 0; i < (A.size()/2-1); i++) {
            if ((i+1) == h) continue;
            res.push_back(i);
            res.push_back(A.size() - 1 - i);
        }
        res.push_back(A.size() / 2);
        res.push_back(A.size() - 1 - h);
    }

    return res;
}