/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 */

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define sz(a) (int)(a).size()

int cnt_emin, cnt_build;

struct WeakHeap {
  // root = 0, a[root] = min
  // i -> { left = 2i + r[i], right = 2i + !r[i], parent = i / 2 }
  vector<int> a, r;

  WeakHeap( int n = 0 ) { // construct empty heap
    a.reserve(n);
    r.reserve(n);
  }

  int ancestor( int i ) {
    int j;
    for (j = i; (j & 1) == r[j >> 1]; j >>= 1) // пока мы -- левый сын
      ; 
    return j >> 1;
  }

  WeakHeap( int n, int *b ) { // construct heap in O(n)
    a = vector<int>(b, b + n);
    r = vector<int>(n, 0);
    for (int i = sz(a) - 1, j; i > 0; i--) 
      if (a[j = ancestor(i)] > a[i]) 
        swap(a[j], a[i]), r[i] ^= 1;
  }

  void add( int x ) { // O(logn)
    a.push_back(x), r.push_back(0);
    for (int i = sz(a) - 1, j; i > 0 && (a[j = ancestor(i)] > a[i]); i = j) 
      swap(a[j], a[i]);
  }

  void emin() { // O(logn)
    int i, j, x = a.back();
    a.pop_back(), r.pop_back();
    if (!sz(a)) 
      return;
    for (i = 1; (j = 2 * i + r[i]) < sz(a); i = j) // спускаемся до упора влево
      ;
    for (; i >= 1; i >>= 1) 
      if (x > a[i]) 
        swap(a[i], x), r[i] ^= 1;
    a[i] = x;
  }
};