#include <bits/stdc++.h>
#define FOR(i,a,b) for(__typeof(b) i=a; i<(b); ++i)
#define FOR0(i,b) for(__typeof(b) i=0; i<(b); ++i)
#define FOR1(i,b) for(__typeof(b) i=1; i<=(b); ++i)
#define TRAV(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define RTRAV(it,c) for(__typeof((c).rbegin()) it=(c).rbegin(); it!=(c).rend(); ++it)
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef vector<vi> vii;
typedef vector<pii> vpii;
typedef long long ll;

#define N 1000000
int v1[N+10];
int v2[N+10];
int v3[N+10];
int v4[N+10];
int v5[N+10];
int v6[N+10];
int v7[N+10];
int n = N;
bool swap_equal = true;

void insertion_sort(int v[], int n){
    FOR(i, 1, n){
        for(int j =i; j && v[j] < v[j-1]; --j) swap(v[j], v[j-1]);
    }
}

void Quicksort1(int v[], int n){
    if(n<=1) return;

    int p1 = rand()%n;  //escolhe um pivo aleatoriamente
    swap(v[0],v[p1]);

    int l = 1;  // invariante: para todo x < i, v[x] < v[p]
    FOR(j,1,n){
         if( v[j] < v[0] ) swap(v[j], v[l++]);  // manuntencao da invariante
         else if ( v[j] == v[0] ){  // quando o elemento for igual, alterna o lado no qual ele eh jogado para evitar a geracao de particoes desbalanceadas
             if( swap_equal ) swap(v[j], v[l++]);
             swap_equal = !swap_equal;
        }
    }

    swap(v[0], v[l-1]);
    p1 = l-1;   //nova posicao do pivo

    Quicksort1(v, p1);  //orderna primeira metade
    Quicksort1(v+p1+1, n - p1 - 1 ); //ordena segunda metade
}

int auxpivots[10];
void get_pivots(int v[], int n, int num_pivots){

    auxpivots[0] = rand()%n;
    FOR(i,1,num_pivots*2 + 1){

        while( true ){
            int next_pivot = rand()%n;
            bool dif = true;
            FOR0(j,i+1) if( next_pivot == auxpivots[j] ){
                dif = false;
                break;
            }
            if( dif ){
                auxpivots[i] = next_pivot;
                break;
            }
        }
    }

    FOR(i, 1, num_pivots*2 + 1){
        for(int j =i; j && v[  auxpivots[j] ] < v[  auxpivots[j-1] ]; --j) swap(auxpivots[j], auxpivots[j-1]);
    }

}

void QuicksortH1(int v[], int n){

    if(n<=17){
        insertion_sort(v,n);
        return;
    }

    get_pivots(v,n,1);
    int p = auxpivots[1]; //escolhe pivot segundo criterio solicitado
    swap(v[0],v[p]);

    int l = 1;  // invariante: para todo x < i, v[x] < v[p]
    FOR(j,1,n){
         if( v[j] < v[0] ) swap(v[j], v[l++]);  // manuntencao da invariante
         else if ( v[j] == v[0] ){  // quando o elemento for igual, alterna o lado no qual ele eh jogado para evitar a geracao de particoes desbalanceadas
             if( swap_equal ) swap(v[j], v[l++]);
             swap_equal = !swap_equal;
        }
    }

    swap(v[0], v[l-1]);
    p = l-1;    //nova posicao do pivo

    QuicksortH1(v, p);  //orderna primeira metade
    QuicksortH1(v+p+1, n - p - 1 ); //ordena segunda metade
}

int dual_pivotation(int v[], int n, int& l, int& r){

    if( v[0] > v[n-1] ) swap(v[0], v[n-1]);

    int vp1 = v[0];
    int vp2 = v[n-1];

    //invariante: para todo x < l e y > r, v[x] < vp1 e v[y] > vp2
    l = 1;
    int i = 1;
    r = n-2;

    while( i<=r ){
        if( v[i] < vp1 ){   //manuntencao da invariante
            swap( v[i++], v[l++] );
        }
        else if( v[i] > vp2 ){  //manuntencao da invariante
            swap( v[i], v[r--] );
        }
        else{   //  vp1 <= v[i] <= vp2, apenas avance, invariante nao eh violada
            ++i;
        }
    }

    swap(v[0], v[--l]);
    swap( v[n-1], v[++r] );
}

void Quicksort2(int v[], int n){

    if(n<=1) return;

    int p1,p2;
    dual_pivotation(v,n,p1,p2);

    Quicksort2(v, p1);  //ordena vetor com elementos cujos valores sao menor que o pivot 1
    Quicksort2(v + p1 + 1, p2 - p1 - 1);    // ordenada valores entre p1 e p2, inclusive
    Quicksort2(v+p2+1, n-p2-1); //ordena valores maiores que p2
}

void QuicksortH2(int v[], int n){

    if(n<=17){
        insertion_sort(v,n);
        return;
    }

    int p1,p2;
    get_pivots(v,n,2);
    p1 = auxpivots[1];  //pivo 1
    p2 = auxpivots[3];  // pivo 2
    // v[p1] <= v[p2]

    //posiciona os pivos escolhidos nos extremos do vetor a fim de facilitar o pivoteamento
    swap(v[0], v[p1]);
    swap(v[n-1], v[p2]);

    dual_pivotation(v,n,p1,p2);
    //p1 e p2 agora possuem as novas posicoes dos pivos

    QuicksortH2(v, p1); //ordena vetor com elementos cujos valores sao menor que o pivot 1
    QuicksortH2(v + p1 + 1, p2 - p1 - 1);   // ordenada valores entre p1 e p2, inclusive
    QuicksortH2(v+p2+1, n-p2-1);    //ordena valores maiores que p2
}

void triple_partition(int v[], int n, int& p1, int& p2, int& p3){
    int a = 2;
    int b = 2;
    int c = n-2;
    int d = n-2;
    int p = v[0], q = v[1], r = v[n-1];
    while( b<=c ){
        while( v[b] < q && b <=c ){
            if( v[b] < p ){
                swap(v[a], v[b]);
                ++a;
            }
            ++b;
        }
        while( v[c] > q && b <= c ){
            if( v[c] > r ){
                swap(v[c], v[d]);
                --d;
            }
            --c;
        }
        if( b<= c ){
            if( v[b] > r ){
                if( v[c] < p ){
                    swap(v[b], v[a]);
                    swap(v[a], v[c]);
                    ++a;
                }
                else{
                    swap(v[b], v[c]);
                }
                swap(v[c], v[d]);
                ++b;
                --c;
                --d;
            }
            else{
                if( v[c] < p ){
                    swap(v[b], v[a]);
                    swap(v[a], v[c]);
                    ++a;
                }
                else{
                    swap(v[b], v[c]);
                }
                ++b;
                --c;
            }
        }
    }
    --a;
    --b;
    ++c;
    ++d;
    swap(v[1], v[a]);
    swap(v[a], v[b]);
    p2 = b;
    --a;
    swap(v[0], v[a]);
    p1 = a;
    swap(v[n-1], v[d]);
    p3 = d;

}

void Quicksort3(int v[], int n){

    if(n<=1) return;    // um vetor com um unico elemento ja esta ordenado, nao faca nada
    if( n==2 ){
        if( v[0] > v[1] ) swap(v[0], v[1]); // ordenacao de um vetor de 2 elementos eh trivial
        return;
    }

    //garantindo pivo1 <= pivo2 <= pivo3
    if( v[0] > v[1] ) swap(v[0],v[1]);
    if( v[1] > v[n-1] ) swap(v[1], v[n-1]);
    if( v[0] > v[1] ) swap(v[0], v[1]);

    int p1,p2,p3;
    triple_partition(v,n,p1,p2,p3);
    //p1,p2,p3 agora possuem as novas posicoes dos pivos

    //ordena as quatro partes
    Quicksort3(v,p1);
    Quicksort3(v + p1 + 1 , p2 - p1 -1 );
    Quicksort3(v + p2 + 1, p3 - p2 - 1 );
    Quicksort3(v + p3 + 1, n - p3 -1 );
}

void QuicksortH3(int v[], int n){

    if(n<=17){
        insertion_sort(v,n);
        return ;
    }

    int p1,p2,p3;
    get_pivots(v, n, 3);
    p1 = auxpivots[1];  //pivo 1
    p2 = auxpivots[3];  // pivo 2
    p3 = auxpivots[5];  //pivo 3
    //posiciona os pivos escolhidos nos extremos do vetor a fim de facilitar o pivoteamento
    swap(v[0], v[p1]);
    swap(v[1], v[p2]);
    swap(v[n-1], v[p3]);

    //garantindo pivo1 <= pivo2 <= pivo3
    if( v[0] > v[1] ) swap(v[0],v[1]);
    if( v[1] > v[n-1] ) swap(v[1], v[n-1]);
    if( v[0] > v[1] ) swap(v[0], v[1]);

    triple_partition(v,n,p1,p2,p3);
    //p1,p2,p3 agora possuem as novas posicoes dos pivos

    //ordena as quatro partes
    QuicksortH3(v,p1);
    QuicksortH3(v + p1 + 1 , p2 - p1 -1 );
    QuicksortH3(v + p2 + 1, p3 - p2 - 1 );
    QuicksortH3(v + p3 + 1, n - p3 -1 );
}

int main(){
    srand( time(NULL) );

    FOR0(i,n) v1[i] = v2[i] = v3[i] = v4[i] = v5[i] = v6[i] = v7[i] = ( rand()%2000000000 * ( rand()%2 ? 1 : -1 ) );

    ll a = clock();
    sort(v1,v1+n);
    cout << "c++ sort took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    Quicksort1(v2, n);
    cout << "quicksort1 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    QuicksortH1(v5, n);
    cout << "quicksorth1 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    Quicksort2(v3, n);
    cout << "quicksort2 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    QuicksortH2(v6, n);
    cout << "quicksorth2 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    Quicksort3(v4, n);
    cout << "quicksort3 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    a = clock();
    QuicksortH3(v7, n);
    cout << "quicksorth3 took: " << (double)(clock() - a)/CLOCKS_PER_SEC << " s\n";

    bool accepted = true;
    FOR0(i, n) if( v1[i] != v2[i] || v1[i] != v3[i] || v1[i] != v4[i] || v1[i] != v5[i] || v1[i] != v6[i] || v1[i] != v7[i] ){
        accepted = false;
        break;
    }

    if( accepted ) cout << "Accepted\n";
    else cout << "Wrong Answer\n";

    return 0;
}