15
561 88 137 224 640 692 891 16 749 145 78 301 471 525 668

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define maxn 100010
#define NONE 100000000
int key[maxn], s[maxn], left[maxn], right[maxn], d[maxn];
int tt, q, root;

inline void right_rotate(int &t)
{
    int k;
    k = left[t];
    left[t] = right[k];
    right[k] = t;
    s[k] = s[t];
    s[t] = s[left[t]] + s[right[t]] + 1;
    t = k;
}

void left_rotate(int &t)
{
    int k;
    k = right[t];
    right[t] = left[k];
    left[k] = t;
    s[k] = s[t];
    s[t] = s[left[t]] + s[right[t]] + 1;
    t = k;
}

void maintain(int &t, bool flag)
{
    if (t == 0) return;
    if (!flag)
    {
        if (s[left[left[t]]] > s[right[t]])
        {
            right_rotate(t);
        }
        else if (s[right[left[t]] > s[right[t]]])
        {
            left_rotate(left[t]);
            right_rotate(t);
        }
        else return;
    }
    else
    {
        if (s[right[right[t]]] > s[left[t]])
        {
            left_rotate(t);
        }
        else if(s[left[right[t]]] > s[left[t]])
        {
            right_rotate(right[t]);
            left_rotate(t);
        }
        else return;
    }
    maintain(left[t], false);
    maintain(right[t], true);
    maintain(t, false);
    maintain(t, true);
}

void insert(int &t, int &v)
{
    if (t == 0)
    {
        ++tt;
        t = tt;
        key[t] = v;
        s[t] = 1;
        left[t] = right[t] = 0;
    }
    else
    {
        ++s[t];
        if (v < key[t])
            insert(left[t], v);
        else
            insert(right[t], v);
        maintain(t, v >= key[t]);
    }
}

int main()
{
    int n, i;
    while(scanf("%d", &n) != EOF)
    {
        tt = 0;
        root = 0;
        s[0] = 0;
        for (i = 0; i < n; ++i)
            scanf("%d", &d[i]);
        for (i = n - 1; i >= 0; --i)
        {
            insert(root, d[i]);
        }
    }
    printf("why!");
    return 0;
}