#include<bits/stdc++.h>
using namespace std;
 
int main()
{
 
 vector<int> array = {1,4,745,3456,34,2,54,4};
    vector<int> array1 = {1,4,745,3456,34,2,54,4};
    //sort(array.begin(),array.end());
    //sort(array1.rbegin(),array1.rend());
    int h = (int) floor((array.size()-1)/2);
    vector<int> a1(array.begin(), array.begin()+ h);
    vector<int> a2(array.begin() + h, array.end());
    merge(a1.begin(),a1.end(),a2.begin(),a2.end(),array.begin());
    for (long long unsigned int i = 0; i < array.size(); i++){
        cout << array[i] << " ";
    }
    for (long long unsigned int i = 0; i < array1.size(); i++){
        cout << array1[i] << " ";
        cout <<"\n"; 
    }
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewoKIHZlY3RvcjxpbnQ+IGFycmF5ID0gezEsNCw3NDUsMzQ1NiwzNCwyLDU0LDR9OwogICAgdmVjdG9yPGludD4gYXJyYXkxID0gezEsNCw3NDUsMzQ1NiwzNCwyLDU0LDR9OwogICAgLy9zb3J0KGFycmF5LmJlZ2luKCksYXJyYXkuZW5kKCkpOwogICAgLy9zb3J0KGFycmF5MS5yYmVnaW4oKSxhcnJheTEucmVuZCgpKTsKICAgIGludCBoID0gKGludCkgZmxvb3IoKGFycmF5LnNpemUoKS0xKS8yKTsKICAgIHZlY3RvcjxpbnQ+IGExKGFycmF5LmJlZ2luKCksIGFycmF5LmJlZ2luKCkrIGgpOwogICAgdmVjdG9yPGludD4gYTIoYXJyYXkuYmVnaW4oKSArIGgsIGFycmF5LmVuZCgpKTsKICAgIG1lcmdlKGExLmJlZ2luKCksYTEuZW5kKCksYTIuYmVnaW4oKSxhMi5lbmQoKSxhcnJheS5iZWdpbigpKTsKICAgIGZvciAobG9uZyBsb25nIHVuc2lnbmVkIGludCBpID0gMDsgaSA8IGFycmF5LnNpemUoKTsgaSsrKXsKICAgICAgICBjb3V0IDw8IGFycmF5W2ldIDw8ICIgIjsKICAgIH0KICAgIGZvciAobG9uZyBsb25nIHVuc2lnbmVkIGludCBpID0gMDsgaSA8IGFycmF5MS5zaXplKCk7IGkrKyl7CiAgICAgICAgY291dCA8PCBhcnJheTFbaV0gPDwgIiAiOwogICAgICAgIGNvdXQgPDwiXG4iOyAKICAgIH0KfQ==