include iostream include iomanip include cstdio include string include

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <ctime>
#include <random>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
#define PATH "D:\\QtProjects\\olymp\\"
template <class T> void mx(T& a, const T& b) { if (a < b) a = b; }
template <class T> void mn(T& a, const T& b) { if (a > b) a = b; }

typedef tree<int, null_type> TREE;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> TREE2;

struct item {
  int key, prior;
  item * l, * r;
  item() { }
  item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item * pitem;

void split (pitem t, int key, pitem & l, pitem & r) {
  if (!t)
    l = r = NULL;
  else if (key < t->key)
    split (t->l, key, l, t->l),  r = t;
  else
    split (t->r, key, t->r, r),  l = t;
}

void insert (pitem & t, pitem it) {
  if (!t)
    t = it;
  else if (it->prior > t->prior)
    split (t, it->key, it->l, it->r),  t = it;
  else
    insert (it->key < t->key ? t->l : t->r, it);
}

void merge (pitem & t, pitem l, pitem r) {
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge (l->r, l->r, r),  t = l;
  else
    merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
  if (t->key == key)
    merge (t, t->l, t->r);
  else
    erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
  if (!l || !r)  return l ? l : r;
  if (l->prior < r->prior)  swap (l, r);
  pitem lt, rt;
  split (r, l->key, lt, rt);
  l->l = unite (l->l, lt);
  l->r = unite (l->r, rt);
  return l;
}


const int N = 1e6;
int rnds[N];
int main(){
  //freopen(PATH"input.txt", "r", stdin);
  ios_base::sync_with_stdio(false);
  TREE2 ss;
  set<int> sset;
  srand(clock());
  for (int i = 0; i < N; ++i)
    rnds[i] = (rand() << 15) + rand();

  clock_t curt = clock();
  for (int i = 0; i < N; ++i)
    ss.insert(rnds[i]);
  clock_t curt2 = clock();
  cout << "inserttime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
  curt = clock();

  curt = clock();
  for (int i = 0; i < N; ++i)
    sset.insert(rnds[i]);
  curt2 = clock();
  cout << "inserttime set:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;

  cout << "sizes" << sset.size() << ' ' << ss.size() << endl;

  curt = clock();
  pitem rt = NULL;
  for (int i = 0; i < N; ++i)
    insert(rt, new item(rnds[i], (rand() << 15) & rand()));
  curt2 = clock();
  cout << "inserttime treap:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;



  curt = clock();
  for (int i = 0; i < N; ++i)
    rnds[i] = *ss.find_by_order(i);
  curt2 = clock();
  cout << "foundtime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;

  curt = clock();
  int i = 0;
  for (auto it = ss.begin(); it != ss.end(); ++it)
    rnds[i++] = *it;
  curt2 = clock();
  cout << "gothroughtime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;

  curt = clock();
  i = 0;
  for (auto it = sset.begin(); it != sset.end(); ++it)
    rnds[i++] = *it;
  curt2 = clock();
  cout << "gothroughtime set:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;

  for (int i = 1; i < N; ++i)
    assert(rnds[i] >= rnds[i - 1]);

  return 0;
}