#include <iostream>
#include <algorithm>
using namespace std;
void showarray(int a[], int c, int d)
{
    for (int i = 0; i < c; ++i)
        cout << a[i] << ' ';
    cout <<  endl;
}
//对a[low]到a[high]由小到大排序
bool QuickSort(int a[], int count, int teamIdx)
{
    if (teamIdx == 0x1){
        showarray(a, count, teamIdx);
        return false;
    }
    int mid = a[count / 2];
    int i = 0, j = count - 1;
    do{
        while (a[i] <= mid) ++i;
        while (a[j] > mid) --j;

        if (i >= j) break;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    } while (true);

    if (count <= 2) return true;
    if ((i > 1) && QuickSort(a, i, (teamIdx << 1) | 0)) return false;
    if ((count - i > 1) && QuickSort(a + i, count - i, (teamIdx << 1) | 1)) return false;
    return true;
}

int main()
{
    int a[] = { 10, 6, 2, 7, 14, 4, 1, 13, 8, 15, 5, 3, 9, 11, 12, 16 };
    cout << "array:"; showarray(a, _countof(a), 0);
    QuickSort(a, _countof(a), 0);


    int b[] = { 49, 38, 65, 97, 76, 13, 27, 50, 2, 8 };
    cout << "array:"; showarray(b, _countof(b), 0);
    QuickSort(b, _countof(b), 0);

    int cnt = 0;
    int c[300];
    cin >> cnt;
    for (int i = 0; i < cnt; cin >> c[i++]);
    showarray(c, cnt, 0);
    QuickSort(c, cnt, 0);
}