// #include "partition.h"
// #include<vector>
// #include<iostream>
// #include<map>
// #include<set>
// 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);
        }
    }
    std::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 = (long long) n * (n + 1) / 2;
        sm = (sm + 1) / 2;
        std::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 <= 1000; n++) {
//         vector<int> a;
//         set<int> all;
//         for (int j = 1; j <= n; j++) {
//             a.push_back(j);
//         }
//         long long at_least = (n * (n + 1) / 2 + 1) / 2, cnt = 0, sm = 0;
//         for (auto k : solve(a)) {
//             all.insert(k);
//         }
//         if (all.size() != n || *all.rbegin() != n - 1) {
//             throw(0);
//         }
//         for (auto k : solve(a)) {
//             k++;
//             cnt++;
//             sm += k;
//             if (sm >= at_least) {
//                 break;
//             }
//         }
//         // for (auto k : solve(a)) {
//         //     cout << k << " ";
//         // }
//         // cout << endl;
//         cout << cnt << " " << n << endl;
//         if (cnt != n / 2 && n % 2 == 0) {
//             cout << "BAD " << n << endl;
//             throw(0);
//         }
//         if (cnt != n / 2 && cnt != (n + 1) / 2 && n % 2 == 1) {
//             cout << "BAD " << n << endl;
//             throw(0);
//         }

//     }
// }