#include <iostream>
#include <vector>
#include <algorithm>
 
 
void printVect(const std::vector<int> path) {
    for( std::vector<int>::const_iterator i = path.begin(); i != path.end(); ++i) {
        std::cout << *i << ' ';
    }
    std::cout << "\n";
}
 
int moveTo(const int index, const int right) {
    const int shift = index >> 1;
    return ((index & 1) == 0) ? shift : (right - shift);
}
 
template<class T>
int rotate(std::vector<T>& nums, const int start, std::vector<bool>& seen) {
 
    const int right = nums.size() - 1;
 
    int index = start;
    T buffer = nums[index];
    int count = 0;
 
    do {
        const int npos = moveTo(index, right);
        const T tmp = nums[npos];
        nums[npos] = buffer;
        buffer = tmp;
        index = npos;
        count++;
        seen[npos] = true;
    } while (index != start);
 
    return count;
}
 
template<class T>
void shuffleEvenOdd(std::vector<T>& nums) {
 
    const int sz = nums.size();
    if (sz < 3) {
        return;
    }
 
    std::vector<bool> seen = std::vector<bool>(sz, false);
 
    int count = 0;
    for (int i = 0; i < sz && count < sz; i++) {
        if (!seen[i]) {
            count += rotate(nums, i, seen);
        }
    }
 
}
 
void prepareEntries(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
}
 
void test( std::vector<int>& input, const std::vector<int>& expected, const std::string & testName)
{
    std::cout << "Test case : " << testName << "\n";
    std::cout << "Input : ";
    printVect(input);
 
    prepareEntries(input);
    std::cout << "Prepd : ";
    printVect(input);
 
    shuffleEvenOdd(input);
    std::cout << "Output: ";
    printVect(input);
    std::cout << "Expect: ";
    printVect(expected);
 
    std::cout << (expected == input ? " correct\n" : " !!!FAILED!!!\n");
 
    std::cout<<"\n\n";
}
 
void test1()
{
    std::vector<int>tmp= {2,2,2};
    const std::vector<int>expected= {2,2,2};
    const std::string tstName = " Test 1 ";
 
    test(tmp,expected, tstName);
}
 
void test2()
{
    std::vector<int>tmp= {2};
    const std::vector<int>expected= {2};
    const std::string tstName = " Test 2 ";
 
    test(tmp,expected, tstName);
}
 
void test3()
{
    std::vector<int>tmp= {3,3};
    const std::vector<int>expected= {3,3};
    const std::string tstName = " Test 3 ";
 
    test(tmp,expected, tstName);
}
 
void test4()
{
    std::vector<int>tmp= {1,-8,2,0,5};
    const std::vector<int>expected= {-8,1,5,2,0};
    const std::string tstName = " Test 4 ";
 
    test(tmp,expected, tstName);
}
 
void test5()
{
    std::vector<int>tmp= {-9,1,-8,2,0,5};
    const std::vector<int>expected= {-9,0,2,5,1,-8};
    const std::string tstName = " Test 5 ";
 
    test(tmp,expected, tstName);
}
 
 
void test6()
{
    std::vector<int> tmp = std::vector<int>(100);
    std::vector<int> expect = std::vector<int>(100);
    for (int i = 0; i < 100; i++) {
        tmp[i] = i;
        int os = i >> 1;
        expect[((i & 1) == 1) ? (99 - os) : os] = i;
    }
    const std::string name = " Sequentials 5";
 
    test(tmp, expect, name);
 
}
 
int main()
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
 
    return 0;
}
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKCnZvaWQgcHJpbnRWZWN0KGNvbnN0IHN0ZDo6dmVjdG9yPGludD4gcGF0aCkgewogICAgZm9yKCBzdGQ6OnZlY3RvcjxpbnQ+Ojpjb25zdF9pdGVyYXRvciBpID0gcGF0aC5iZWdpbigpOyBpICE9IHBhdGguZW5kKCk7ICsraSkgewogICAgICAgIHN0ZDo6Y291dCA8PCAqaSA8PCAnICc7CiAgICB9CiAgICBzdGQ6OmNvdXQgPDwgIlxuIjsKfQoKaW50IG1vdmVUbyhjb25zdCBpbnQgaW5kZXgsIGNvbnN0IGludCByaWdodCkgewogICAgY29uc3QgaW50IHNoaWZ0ID0gaW5kZXggPj4gMTsKICAgIHJldHVybiAoKGluZGV4ICYgMSkgPT0gMCkgPyBzaGlmdCA6IChyaWdodCAtIHNoaWZ0KTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4KaW50IHJvdGF0ZShzdGQ6OnZlY3RvcjxUPiYgbnVtcywgY29uc3QgaW50IHN0YXJ0LCBzdGQ6OnZlY3Rvcjxib29sPiYgc2VlbikgewoKICAgIGNvbnN0IGludCByaWdodCA9IG51bXMuc2l6ZSgpIC0gMTsKCiAgICBpbnQgaW5kZXggPSBzdGFydDsKICAgIFQgYnVmZmVyID0gbnVtc1tpbmRleF07CiAgICBpbnQgY291bnQgPSAwOwoKICAgIGRvIHsKICAgICAgICBjb25zdCBpbnQgbnBvcyA9IG1vdmVUbyhpbmRleCwgcmlnaHQpOwogICAgICAgIGNvbnN0IFQgdG1wID0gbnVtc1tucG9zXTsKICAgICAgICBudW1zW25wb3NdID0gYnVmZmVyOwogICAgICAgIGJ1ZmZlciA9IHRtcDsKICAgICAgICBpbmRleCA9IG5wb3M7CiAgICAgICAgY291bnQrKzsKICAgICAgICBzZWVuW25wb3NdID0gdHJ1ZTsKICAgIH0gd2hpbGUgKGluZGV4ICE9IHN0YXJ0KTsKCiAgICByZXR1cm4gY291bnQ7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+CnZvaWQgc2h1ZmZsZUV2ZW5PZGQoc3RkOjp2ZWN0b3I8VD4mIG51bXMpIHsKCiAgICBjb25zdCBpbnQgc3ogPSBudW1zLnNpemUoKTsKICAgIGlmIChzeiA8IDMpIHsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgc3RkOjp2ZWN0b3I8Ym9vbD4gc2VlbiA9IHN0ZDo6dmVjdG9yPGJvb2w+KHN6LCBmYWxzZSk7CgogICAgaW50IGNvdW50ID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc3ogJiYgY291bnQgPCBzejsgaSsrKSB7CiAgICAgICAgaWYgKCFzZWVuW2ldKSB7CiAgICAgICAgICAgIGNvdW50ICs9IHJvdGF0ZShudW1zLCBpLCBzZWVuKTsKICAgICAgICB9CiAgICB9Cgp9Cgp2b2lkIHByZXBhcmVFbnRyaWVzKHN0ZDo6dmVjdG9yPGludD4mIG51bXMpIHsKICAgIHN0ZDo6c29ydChudW1zLmJlZ2luKCksIG51bXMuZW5kKCkpOwp9Cgp2b2lkIHRlc3QoIHN0ZDo6dmVjdG9yPGludD4mIGlucHV0LCBjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+JiBleHBlY3RlZCwgY29uc3Qgc3RkOjpzdHJpbmcgJiB0ZXN0TmFtZSkKewogICAgc3RkOjpjb3V0IDw8ICJUZXN0IGNhc2UgOiAiIDw8IHRlc3ROYW1lIDw8ICJcbiI7CiAgICBzdGQ6OmNvdXQgPDwgIklucHV0IDogIjsKICAgIHByaW50VmVjdChpbnB1dCk7CgogICAgcHJlcGFyZUVudHJpZXMoaW5wdXQpOwogICAgc3RkOjpjb3V0IDw8ICJQcmVwZCA6ICI7CiAgICBwcmludFZlY3QoaW5wdXQpOwoKICAgIHNodWZmbGVFdmVuT2RkKGlucHV0KTsKICAgIHN0ZDo6Y291dCA8PCAiT3V0cHV0OiAiOwogICAgcHJpbnRWZWN0KGlucHV0KTsKICAgIHN0ZDo6Y291dCA8PCAiRXhwZWN0OiAiOwogICAgcHJpbnRWZWN0KGV4cGVjdGVkKTsKCiAgICBzdGQ6OmNvdXQgPDwgKGV4cGVjdGVkID09IGlucHV0ID8gIiBjb3JyZWN0XG4iIDogIiAhISFGQUlMRUQhISFcbiIpOwoKICAgIHN0ZDo6Y291dDw8IlxuXG4iOwp9Cgp2b2lkIHRlc3QxKCkKewogICAgc3RkOjp2ZWN0b3I8aW50PnRtcD0gezIsMiwyfTsKICAgIGNvbnN0IHN0ZDo6dmVjdG9yPGludD5leHBlY3RlZD0gezIsMiwyfTsKICAgIGNvbnN0IHN0ZDo6c3RyaW5nIHRzdE5hbWUgPSAiIFRlc3QgMSAiOwoKICAgIHRlc3QodG1wLGV4cGVjdGVkLCB0c3ROYW1lKTsKfQoKdm9pZCB0ZXN0MigpCnsKICAgIHN0ZDo6dmVjdG9yPGludD50bXA9IHsyfTsKICAgIGNvbnN0IHN0ZDo6dmVjdG9yPGludD5leHBlY3RlZD0gezJ9OwogICAgY29uc3Qgc3RkOjpzdHJpbmcgdHN0TmFtZSA9ICIgVGVzdCAyICI7CgogICAgdGVzdCh0bXAsZXhwZWN0ZWQsIHRzdE5hbWUpOwp9Cgp2b2lkIHRlc3QzKCkKewogICAgc3RkOjp2ZWN0b3I8aW50PnRtcD0gezMsM307CiAgICBjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+ZXhwZWN0ZWQ9IHszLDN9OwogICAgY29uc3Qgc3RkOjpzdHJpbmcgdHN0TmFtZSA9ICIgVGVzdCAzICI7CgogICAgdGVzdCh0bXAsZXhwZWN0ZWQsIHRzdE5hbWUpOwp9Cgp2b2lkIHRlc3Q0KCkKewogICAgc3RkOjp2ZWN0b3I8aW50PnRtcD0gezEsLTgsMiwwLDV9OwogICAgY29uc3Qgc3RkOjp2ZWN0b3I8aW50PmV4cGVjdGVkPSB7LTgsMSw1LDIsMH07CiAgICBjb25zdCBzdGQ6OnN0cmluZyB0c3ROYW1lID0gIiBUZXN0IDQgIjsKCiAgICB0ZXN0KHRtcCxleHBlY3RlZCwgdHN0TmFtZSk7Cn0KCnZvaWQgdGVzdDUoKQp7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+dG1wPSB7LTksMSwtOCwyLDAsNX07CiAgICBjb25zdCBzdGQ6OnZlY3RvcjxpbnQ+ZXhwZWN0ZWQ9IHstOSwwLDIsNSwxLC04fTsKICAgIGNvbnN0IHN0ZDo6c3RyaW5nIHRzdE5hbWUgPSAiIFRlc3QgNSAiOwoKICAgIHRlc3QodG1wLGV4cGVjdGVkLCB0c3ROYW1lKTsKfQoKCnZvaWQgdGVzdDYoKQp7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IHRtcCA9IHN0ZDo6dmVjdG9yPGludD4oMTAwKTsKICAgIHN0ZDo6dmVjdG9yPGludD4gZXhwZWN0ID0gc3RkOjp2ZWN0b3I8aW50PigxMDApOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAxMDA7IGkrKykgewogICAgICAgIHRtcFtpXSA9IGk7CiAgICAgICAgaW50IG9zID0gaSA+PiAxOwogICAgICAgIGV4cGVjdFsoKGkgJiAxKSA9PSAxKSA/ICg5OSAtIG9zKSA6IG9zXSA9IGk7CiAgICB9CiAgICBjb25zdCBzdGQ6OnN0cmluZyBuYW1lID0gIiBTZXF1ZW50aWFscyA1IjsKCiAgICB0ZXN0KHRtcCwgZXhwZWN0LCBuYW1lKTsKCn0KCmludCBtYWluKCkKewogICAgdGVzdDEoKTsKICAgIHRlc3QyKCk7CiAgICB0ZXN0MygpOwogICAgdGVzdDQoKTsKICAgIHRlc3Q1KCk7CiAgICB0ZXN0NigpOwoKICAgIHJldHVybiAwOwp9Cgo=