#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <array>
#include <iomanip>
#include <experimental/optional>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <random>
#include <functional>
#include <array>
#include <initializer_list>

namespace vectree { namespace detail { namespace treap {

template<class T>
class node
{
  T value_;
  node<T> *lch_, *rch_;
  double priority_;
  unsigned tree_size_;

  enum class side
  { left, right, none };

  static constexpr auto sibling(side s) noexcept
  { return s == side::right ? side::left : side::right; }

  explicit node(T v, double p)          noexcept
  : value_{v}, lch_{nullptr}, rch_{nullptr}, priority_{p}, tree_size_{1}
  {}

  static auto cut_link(node<T>* parent, side s) -> void;
  static auto set_least_priority(node<T>*& tree, node<T>*& parent, side last_side) -> node<T>*;
  static auto erase_node(node<T>* tree, node<T>* parent, side last_side) -> node<T>*;

public:

  using node_ptr = node<T>*;
  using node_ptr_reference = node_ptr&;
  using node_ptr_const_reference = node_ptr const&;

  ~node()
  {
    if (lch_) delete lch_;
    if (rch_) delete rch_;
  }


  constexpr auto const& priority() const noexcept { return priority_; }

  constexpr auto& value()               noexcept
  { return value_; }

  constexpr auto const& value()   const noexcept
  { return value_; }
  
  constexpr auto size()           const noexcept
  { return tree_size_; }

  constexpr auto expired_left()   const
  { return !lch_; }

  constexpr auto expired_right()  const
  { return !rch_; }

  constexpr auto expired_both()   const
  { return expired_left() && expired_right(); }

  auto left()               -> node_ptr_reference;
  auto left()        const  -> node_ptr_const_reference;
  auto right()              -> node_ptr_reference;
  auto right()       const  -> node_ptr_const_reference;
  auto child(side w)        -> node_ptr_reference;
  auto child(side w) const  -> node_ptr_const_reference;

  auto update_size()                                          -> void;
  static auto rotate(node_ptr tree, side right)               -> node_ptr;
  static auto insert(node_ptr tree, unsigned position, T val) -> node_ptr;
  static auto nth_element(node_ptr tree, unsigned position)   -> node_ptr;
  static auto erase(node_ptr tree, unsigned position) -> node_ptr;
  static auto erase(node_ptr tree, unsigned position, node_ptr parent, side direction) -> node_ptr;

  static auto predecessor(node_ptr t)                         -> node_ptr;
  static auto successor(node_ptr t)                           -> node_ptr;

  static auto create(T val)
  {
    static auto rand_priority_gen = std::bind(
      std::uniform_real_distribution<>{0.0, 1.0},
      std::default_random_engine{});
    return new node(val, rand_priority_gen());
  }

};
}}}

namespace vectree
{

template<class T>
class vectree
{
  using treap    = detail::treap::node<T>;
  using node_ptr = typename treap::node_ptr;

  node_ptr root {nullptr};

public:

  vectree() = default;

  ~vectree()
  {
    if (root) { delete root; }
  }

  auto size() const noexcept
  { return root ? root->size() : 0; }

  T operator[] (unsigned position) const { return treap::nth_element(root, position)->value(); }

  auto insert(unsigned position, T val)
    -> void
  {
    root = treap::insert(root, position, val);
  }

  auto push_back(T val)
    -> void
  {
    root = treap::insert(root, size(), val);
  }

  auto push_front(T val)
    -> void
  {
    root = treap::insert(root, 0, val);
  }

  auto erase(unsigned position)
    -> void
  {
    root = treap::erase(root, position, nullptr);
  }

  auto clear()
    -> void
  {
    if (root) delete root;
    root = nullptr;
  }
};

}


namespace vectree{ namespace detail {namespace treap {

template<class T>
auto node<T>::left()
  -> node<T>::node_ptr_reference
{ return lch_; }

template<class T>
auto node<T>::right()
  -> node<T>::node_ptr_reference
{ return rch_; }

template<class T>
auto node<T>::left() const
  -> node<T>::node_ptr_const_reference
{
  assert(!expired_left());
  return lch_;
}

template<class T>
auto node<T>::right() const
  -> node<T>::node_ptr_const_reference
{
  assert(!expired_right());
  return rch_;
}

template<class T>
auto node<T>::child(side s)
  -> node_ptr_reference
{ return s == side::left ? left() : right(); }

template<class T>
auto node<T>::child(side s) const
  -> node_ptr_const_reference
{ return s == side::left ? left() : right(); }

template<class T>
auto node<T>::update_size()
  -> void
{
  tree_size_ =
    1 + (expired_left()  ? 0 : left()->size())
      + (expired_right() ? 0 : right()->size());
}

template<class T>
auto node<T>::rotate(node<T>::node_ptr tree, side dir)
  -> node<T>::node_ptr
{
  auto const subtree = tree->child(node<T>::sibling(dir));
  tree->child(node<T>::sibling(dir)) = subtree->child(dir);
  subtree->child(dir) = tree;
  tree->update_size();
  subtree->update_size();
  return subtree;
}

template<class T>
auto node<T>::insert(node<T>::node_ptr tree, unsigned position, T val)
  -> node<T>::node_ptr
{
  if (!tree)
  {
    tree = node<T>::create(val);
    tree->update_size();
    return tree;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();
  auto const to_right = left_size < position;

  auto const next_tree = to_right ? tree->right() : tree->left();
  auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
  auto const inserted_subtree = insert(next_tree, subtree_pos, val);

  (to_right ? tree->right() : tree->left()) = inserted_subtree;

  tree->update_size();

  if (tree->priority() < inserted_subtree->priority())
  {
    return rotate(tree, to_right ? side::left : side::right);
  }

  return tree;
}

template<class T>
auto node<T>::cut_link(node<T>::node_ptr parent, side s)
  -> void
{
  (s == side::left ? parent->left() : parent->right()) = nullptr;
}

template<class T>
auto node<T>::set_least_priority(node<T>::node_ptr& deletee, node<T>::node_ptr& parent, side last_side)
  -> node_ptr
{
  puts("start - set_least_priority()");

  node<T>::node_ptr ret {nullptr};

  while (true)
  {
    node<T>::node_ptr ntree {nullptr};
    if (deletee->expired_both())
    {
      puts("expired_both()");
      break;
    }
    else if (deletee->expired_left())
    {
      std::swap(deletee->value(), deletee->right()->value());
      ntree   = deletee;
      deletee = deletee->right();
    }
    else if (deletee->expired_right())
    {
      std::swap(deletee->value(), deletee->left()->value());
      ntree   = deletee;
      deletee = deletee->left();
    }
    else
    {
      auto right_up = deletee->left()->priority() < deletee->right()->priority();
      ntree = rotate(deletee, (last_side = (right_up ? side::left : side::right)));
      ntree->update_size();
    }

    if (!ret)
    {
      ret = ntree;
    }

    if (parent)
    {
      (last_side == side::right ? parent->left() : parent->right()) = ntree;
    }

    parent = ntree;
  }

  puts("end");

  return ret;
}

template<class T>
auto node<T>::erase_node(node<T>::node_ptr deletee, node<T>::node_ptr parent, side last_side)
  -> node_ptr
{
  // ??????????????°????????¨
  node<T>::node_ptr ret {set_least_priority(deletee, parent, last_side)};

  puts("start - cut_link");
  cut_link(parent, last_side);
  puts("end");

  puts("start - delete deletee");
  delete deletee;
  deletee = nullptr;
  puts("end");

  if (parent)
  {
    puts("start - update_size(parent)");
    parent->update_size();
    puts("end");
  }

  return ret;
}

template<class T>
auto node<T>::erase(node<T>::node_ptr tree, unsigned position, node_ptr parent, side direction)
  -> node_ptr
{
  if (!tree)
  {
    return nullptr;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();

  if (left_size == position)
  {
    return erase_node(tree, parent, direction);
  }
  else
  {
    auto const to_right = left_size < position;
    auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
    auto const next_direction = to_right ? side::right : side::left;
    auto r = erase(to_right ? tree->right() : tree->left(), subtree_pos, tree, next_direction);
    (to_right ? tree->right() : tree->left()) = r;
    tree->update_size();
    return tree;
  }
}

template<class T>
auto node<T>::erase(node<T>::node_ptr tree, unsigned position)
  -> node_ptr
{
  return erase(tree, position, nullptr, side::left);
}

template<class T>
auto node<T>::nth_element(node<T>::node_ptr tree, unsigned position)
  -> node<T>::node_ptr
{
  if (!tree)
  {
    return nullptr;
  }

  auto const left_size = tree->expired_left() ? 0 : tree->left()->size();

  if (left_size == position)
  {
    return tree;
  }

  auto const to_right = left_size < position;
  auto const subtree_pos = position - (to_right ? 1 + left_size : 0);
  
  return nth_element(to_right ? tree->right() : tree->left(), subtree_pos);
}

#define TREAP_TEST

#ifdef TREAP_TEST

template<class T>
inline void debug_recur(node<T>* t, int depth = 0) {

  for(int i=0; i<depth * 2; i++)
    std::cout << " ";

  if(!t)
  {
    std::cout << "(nil)" << std::endl;
    return;
  }

  std::cout << "(" << t->value() << "[" << t->priority() << "]" << std::endl;

  debug_recur(t->left(), depth + 1);
  debug_recur(t->right(), depth + 1);

  for(int i=0; i<depth * 2; i++)
  {
    std::cout << " ";
  }

  std::cout << ")" << std::endl;
}

template<class T>
inline void debug(node<T>* t) {
  debug_recur(t);
  std::cout << "\n";
}

inline void test() {
  node<int>* root = nullptr;
  std::vector<int> vs;

  auto assert_identical = [&]()
  {
    assert(vs.size() == root->size());
    for(unsigned i=0; i<vs.size(); i++) {
      assert(vs[i] == node<int>::nth_element(root, i)->value());
    }
  };

  // INSERT
  for(int i=0; i<30; i++)
  {
    auto pos = i;
    auto val = i;
    vs.insert(vs.begin() + pos, val);
    root = node<int>::insert(root, pos, val);
    assert_identical();
  }

  std::cout << "root size = " << root->size() << std::endl;

  for(auto e: vs) std::cout << e << ", ";
  std::cout << std::endl;

  debug(root);

  // ERASE
  for(int i=0; i<3; i++)
  {
    root = node<int>::erase(root, 0);
    root->node<int>::update_size();

    puts("ERASED 0");
    puts("~~~~~~~~~~~~~~~~~");
    debug(root);
    std::cout << "size = " << root->size() << "\n";

    for(unsigned i=0; i<root->size(); i++)
    {
      printf("PRINT %dth element: ", i);
      std::cout << node<int>::nth_element(root, i)->value();
      puts("");
    }
    std::cout << std::endl;
  }

  debug(root);
}

#endif
}}} // namespace treap

#ifndef TREAP_TEST
int main()
{
  vectree::detail::treap::test();
  return 0;
}

#else

int main() {
  int N; std::cin >> N;
  vectree::vectree<int> vs;
  for(int i=0; i<N; i++) {
    int x; std::cin >> x;
    vs.push_front(x);
  }
  for(int i=0; i<N; i++) {
    std::cout << vs[i] << " \n"[i == N-1];
  }
  return 0;
}
#endif

Measured memory_bytes: 3108