template <typename T>
void quickSort(int *a, int low, int high) {
if (low >= high) return;
int l = low, h = high;
int k = a[low];
while (l < h) {
while (l < h && !(a[h] < k)) h--;
if (l < h) a[l++] = a[h];
while (l < h && a[l] < k) l++;
if (l < h) a[h--] = a[l];
}
a[l] = k;
if (l > low) quickSort(a, low, l);
if (l+1 < high) quickSort(a, l+1, high);
}
int pq[MAX_N];
void push(int x) {
int now = ++length;
while (now > 1) {
if (x < pq[now/2]) {
pq[now] = pq[now/2];
now /= 2;
} else
break;
}
pq[now] = x;
}
int pop() {
int ret = pq[1];
int now = 1;
int x = pq[length--];
while (now * 2 <= length) {
int child = now * 2;
if (child + 1 <= length && pq[child+1] < pq[child]) child++;
if (pq[child] < x) {
pq[now] = pq[child];
now = child;
} else
break;
}
pq[now] = x;
return ret;
}