// compile and run with:
// clang++ -stdlib=libc++ main.cpp
// ./a.out 1000000
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "Must specify size\n";
        return 1;
    }
    const int N = atoi(argv[1]);
    if (N <= 0 || N % 4 != 0) {
        std::cerr << "Size must be a positive multiple of 4\n";
        return 1;
    }
    const int k = N / 2;
    std::vector<int> v(N);
    for (int i = 0; i < k; i++) {
        if (i % 2 == 0) {
            v[i] = i;
        } else {
            v[i] = i + k - 1;
        }
    }
    for (int i = k; i < N; i++) {
        v[i] = 2*i - 2*k + 1;
    }
    std::nth_element(v.begin(), v.end() - 1, v.end());

    return 0;
}