#include <set> 
#include <algorithm>    // std::random_shuffle
#include <iostream>
using namespace std;
 
template<class T,size_t N> void view(const T (&ar)[N])
{
    cout<<"ar[]={";
    for(size_t n=0;n<N-1;++n) cout<<ar[n]<<",";
    cout<<ar[N-1]<<"}\n";
}
 
template<class T,size_t N> void mysort(T (&ar)[N])
{
    typedef multiset<T> Myset;
    typedef typename Myset::iterator It;
 
    Myset myset(ar,ar+N);
 
    //отладочный вывод:
    //It it = myset.begin(); size_t n=0;
    //while(it!=myset.end()){ cout<< n<<" : "<< *it<<endl;  ++it;++n; }
    //--------------------------------------------
 
    const size_t num_one = myset.count(1);
    const size_t num_two = myset.count(2);
    const int tail_el = (num_two>num_one)? 2: 1;
 
    const size_t lenbody = min(num_two,num_one);
    const size_t lentail = max(num_two,num_one)-lenbody;
 
	//отладочный вывод:
    //cout<<"number of 1 : "<<num_one<<endl;
    //cout<<"number of 2 : "<<num_two<<endl;
    //cout<<"tail        : "<<lentail<<endl;
    //cout<<"tail_element: "<<tail_el<<endl;
    //cout<<"body        : "<<lenbody<<endl;
    //--------------------------------------------
 
    const size_t size = lenbody*2;
    for(size_t n=0;n<size;n+=2) { ar[n]=1; ar[n+1]=2; }
    for(size_t n=size;n< N; ++n) ar[n]=tail_el;
}
 
 
 
template<class T,size_t N> void test_sort(T (&ar)[N])
{
    std::random_shuffle ( ar, ar+N );
    mysort(ar);
}
 
template<class T> bool check_array(const T (&ar)[15])
{
    int re[]={1,2,1,2,1,2,1,2,1,2,1,2,2,2,2};
    cout<<"expected: \n"; view(re);
 
    size_t n=0;
    while( n<15 && re[n]==ar[n]) ++n;
    return n==15;
}
 
 
 
 
int main() 
{
	cout<<"WELLCOME TO TESTING MY ALGORITHM\n\n";
 
 
    bool all_valid=true;
    for(size_t n=0;n<10;++n) 
    {
        int ar[]={2,1,1,1,2,1,2,2,1,1,2,2,2,2,2};
 
        view(ar);
        test_sort(ar);
        cout<<"actual: \n"; view(ar);
 
        const bool is_valid = check_array(ar);
 
        if(is_valid) cout<<"success!!!!\n";
        else
        {
            cout<< "failed";
            all_valid = false;
        }
    }
 
    cout<< (all_valid? "all testing are valid": "part tests are failed" )<<endl;
	return 0;
}

I2luY2x1ZGUgPHNldD4gCiNpbmNsdWRlIDxhbGdvcml0aG0+ICAgIC8vIHN0ZDo6cmFuZG9tX3NodWZmbGUKI2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGU8Y2xhc3MgVCxzaXplX3QgTj4gdm9pZCB2aWV3KGNvbnN0IFQgKCZhcilbTl0pCnsKICAgIGNvdXQ8PCJhcltdPXsiOwogICAgZm9yKHNpemVfdCBuPTA7bjxOLTE7KytuKSBjb3V0PDxhcltuXTw8IiwiOwogICAgY291dDw8YXJbTi0xXTw8In1cbiI7Cn0KCnRlbXBsYXRlPGNsYXNzIFQsc2l6ZV90IE4+IHZvaWQgbXlzb3J0KFQgKCZhcilbTl0pCnsKICAgIHR5cGVkZWYgbXVsdGlzZXQ8VD4gTXlzZXQ7CiAgICB0eXBlZGVmIHR5cGVuYW1lIE15c2V0OjppdGVyYXRvciBJdDsKCiAgICBNeXNldCBteXNldChhcixhcitOKTsKCiAgICAvL9C+0YLQu9Cw0LTQvtGH0L3Ri9C5INCy0YvQstC+0LQ6CiAgICAvL0l0IGl0ID0gbXlzZXQuYmVnaW4oKTsgc2l6ZV90IG49MDsKICAgIC8vd2hpbGUoaXQhPW15c2V0LmVuZCgpKXsgY291dDw8IG48PCIgOiAiPDwgKml0PDxlbmRsOyAgKytpdDsrK247IH0KICAgIC8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCiAgICBjb25zdCBzaXplX3QgbnVtX29uZSA9IG15c2V0LmNvdW50KDEpOwogICAgY29uc3Qgc2l6ZV90IG51bV90d28gPSBteXNldC5jb3VudCgyKTsKICAgIGNvbnN0IGludCB0YWlsX2VsID0gKG51bV90d28+bnVtX29uZSk/IDI6IDE7CgogICAgY29uc3Qgc2l6ZV90IGxlbmJvZHkgPSBtaW4obnVtX3R3byxudW1fb25lKTsKICAgIGNvbnN0IHNpemVfdCBsZW50YWlsID0gbWF4KG51bV90d28sbnVtX29uZSktbGVuYm9keTsKCgkvL9C+0YLQu9Cw0LTQvtGH0L3Ri9C5INCy0YvQstC+0LQ6CiAgICAvL2NvdXQ8PCJudW1iZXIgb2YgMSA6ICI8PG51bV9vbmU8PGVuZGw7CiAgICAvL2NvdXQ8PCJudW1iZXIgb2YgMiA6ICI8PG51bV90d288PGVuZGw7CiAgICAvL2NvdXQ8PCJ0YWlsICAgICAgICA6ICI8PGxlbnRhaWw8PGVuZGw7CiAgICAvL2NvdXQ8PCJ0YWlsX2VsZW1lbnQ6ICI8PHRhaWxfZWw8PGVuZGw7CiAgICAvL2NvdXQ8PCJib2R5ICAgICAgICA6ICI8PGxlbmJvZHk8PGVuZGw7CiAgICAvLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgogICAgY29uc3Qgc2l6ZV90IHNpemUgPSBsZW5ib2R5KjI7CiAgICBmb3Ioc2l6ZV90IG49MDtuPHNpemU7bis9MikgeyBhcltuXT0xOyBhcltuKzFdPTI7IH0KICAgIGZvcihzaXplX3Qgbj1zaXplO248IE47ICsrbikgYXJbbl09dGFpbF9lbDsKfQoKCgp0ZW1wbGF0ZTxjbGFzcyBULHNpemVfdCBOPiB2b2lkIHRlc3Rfc29ydChUICgmYXIpW05dKQp7CiAgICBzdGQ6OnJhbmRvbV9zaHVmZmxlICggYXIsIGFyK04gKTsKICAgIG15c29ydChhcik7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+IGJvb2wgY2hlY2tfYXJyYXkoY29uc3QgVCAoJmFyKVsxNV0pCnsKICAgIGludCByZVtdPXsxLDIsMSwyLDEsMiwxLDIsMSwyLDEsMiwyLDIsMn07CiAgICBjb3V0PDwiZXhwZWN0ZWQ6IFxuIjsgdmlldyhyZSk7CgogICAgc2l6ZV90IG49MDsKICAgIHdoaWxlKCBuPDE1ICYmIHJlW25dPT1hcltuXSkgKytuOwogICAgcmV0dXJuIG49PTE1Owp9CgoKCgppbnQgbWFpbigpIAp7Cgljb3V0PDwiV0VMTENPTUUgVE8gVEVTVElORyBNWSBBTEdPUklUSE1cblxuIjsKCSAgICAKCiAgICBib29sIGFsbF92YWxpZD10cnVlOwogICAgZm9yKHNpemVfdCBuPTA7bjwxMDsrK24pIAogICAgewogICAgICAgIGludCBhcltdPXsyLDEsMSwxLDIsMSwyLDIsMSwxLDIsMiwyLDIsMn07CgogICAgICAgIHZpZXcoYXIpOwogICAgICAgIHRlc3Rfc29ydChhcik7CiAgICAgICAgY291dDw8ImFjdHVhbDogXG4iOyB2aWV3KGFyKTsKCiAgICAgICAgY29uc3QgYm9vbCBpc192YWxpZCA9IGNoZWNrX2FycmF5KGFyKTsKCiAgICAgICAgaWYoaXNfdmFsaWQpIGNvdXQ8PCJzdWNjZXNzISEhIVxuIjsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBjb3V0PDwgImZhaWxlZCI7CiAgICAgICAgICAgIGFsbF92YWxpZCA9IGZhbHNlOwogICAgICAgIH0KICAgIH0KCiAgICBjb3V0PDwgKGFsbF92YWxpZD8gImFsbCB0ZXN0aW5nIGFyZSB2YWxpZCI6ICJwYXJ0IHRlc3RzIGFyZSBmYWlsZWQiICk8PGVuZGw7CglyZXR1cm4gMDsKfQ==