#include "partition.h"
#include<vector>
#include<iostream>
#include<map>
using namespace std;
std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        if (i + 1 != a[i]) {
            throw(0);
        }
    }
    vector<int> ans;
    if (n % 4 == 0) {
        for (int i = 0; i < n / 2; i++) {
            ans.push_back(i);
            ans.push_back(n - i - 1);
        }
    } else if (n % 4 == 2) {
        long long sm = n * (n + 1) / 2;
        sm = (sm + 1) / 2;
        vector<bool> used(n);
        for (int i = 0; i < n / 2; i++) {
            if (sm - n - 1 >= 0) {
                ans.push_back(i);
                ans.push_back(n - i - 1);
                used[i] = true;
                used[n - i - 1] = true;
                sm -= n + 1;
            } else {
                ans.push_back(n / 2);
                used[n / 2] = true;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                ans.push_back(i);
            }
        }
    } else if (n % 4 == 3) {
        for (int i = 0; i < n / 2; i++) {
            ans.push_back(i);
            ans.push_back(n - i - 2);
        }
        ans.push_back(n - 1);
    } else {
        ans.push_back(0);
        for (int i = 0; i < n / 2; i++) {
            ans.push_back(i + 1);
            ans.push_back(n - i - 1);
        }
    }
    return ans;
}
// int main() {
//     for (long long n = 1; n <= 10000; n++) {
//         vector<int> a;
//         for (int j = 1; j <= n; j++) {
//             a.push_back(j);
//         }
//         long long at_least = (n * (n + 1) / 2 + 1) / 2;
//         for (auto k : solve(a)) {
//             k++;
//             if (at_least > k) {
//                 at_least -= k;
//             } else {
//                 at_least -= k;
//                 break;
//             }
//         }
//         // cout << "BAD " << n << endl;
//         if (at_least != 0 && (n * (n + 1) / 2) % 2 == 0) {
//             throw(0);
//         }
//     }
// }