#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

unsigned R() { return (rand() << 15) + rand(); }

typedef long long ll;

struct T
{
  static T *null;
  int x, y, size;
  T *l, *r;
  ll sum;
  int is_reversed; // reverse [1 2 3] = [3 2 1]

  void down()
  {
    if (is_reversed)
    {
      swap(l, r);
      l->is_reversed ^= 1;
      r->is_reversed ^= 1;
      is_reversed = 0;
    }
  }

  T() { l = r = this, x = 0, size = 0, sum = 0; }
  T( int x, int y, T *l, T *r ) : x(x), y(y), l(l), r(r) { calc(); }
  void calc()
  {
    size = l->size + r->size + (this != null);
    sum = l->sum + r->sum + x;
  }

  void out( int dep = 0 )
  {
    //printf("out: this = %p, dep = %d (null = %p)\n", this, dep, null);
    down();
    if (this == null)
    {
      if (dep == 0)
        puts("<empty>");
      return;
    }
    l->out(dep + 1);
    printf("%*sx = %d, y = %d, size = %d, sum = %I64d\n", 2 * dep, "", x, y, size, sum);
    r->out(dep + 1);
  }

  void out_array()
  {
    if (this == null)
      return;
    l->out_array();
    printf("%d ", x);
    r->out_array();
  }
};

typedef T *Node;

Node T::null = new T();
Node z = T::null, root = z;

void Split( Node t, Node &l, Node &r, int k ) // l = first k elements
{
  t->down();
  if (t == z)
    l = r = z;
  else if (t->l->size >= k)
    Split(t->l, l, t->l, k), r = t;
  else
    Split(t->r, t->r, r, k - t->l->size - 1), l = t;
  l->calc(), r->calc();
}

void Merge( Node &t, Node l, Node r ) // l <= r
{
  l->down();
  r->down();
  if (l == z)
    t = r;
  else if (r == z)
    t = l;
  else if (l->y < r->y)
    t = l, Merge(l->r, l->r, r);
  else
    t = r, Merge(r->l, l, r->l);
  t->calc();
}

void InsertSlow( Node &t, int i, int x, int y )
{
  Node l, r;
  Split(t, l, r, i); // first i
  Merge(l, l, new T(x, y, z, z)); // l + (x)
  Merge(t, l, r); // (first i) + (x) + (last n-i)
}

inline void InsertFast( Node &t, int i, int x, int y )
{
  t->down();
  if (t == z)
    t = new T(x, y, z, z);
  else if (t->y < y)
    if (t->l->size >= i)
      InsertFast(t->l, i, x, y);
    else
      InsertFast(t->r, i - 1 - t->l->size, x, y);
  else
  {
    Node l, r;
    Split(t, l, r, i);
    t = new T(x, y, l, r);
  }
}

inline void DeleteFast( Node &t, int i )
{
  t->down();
  assert(0 <= i && i < t->size); // 0 .. size-1
  if (i != t->l->size)
    if (t->l->size > i)
      DeleteFast(t->l, i);
    else
      DeleteFast(t->r, i - t->l->size - 1);
  else
    Merge(t, t->l, t->r);
}

// [L..R]
ll Sum( Node &t, int L, int R )
{
  Node l, r;
  Split(t, t, r, R + 1);
  Split(t, l, t, L); // L = 0
  ll res = t->sum;
  Merge(t, l, t);
  Merge(t, t, r);
  return res;
}

// [L..R]
void Reverse( Node &t, int L, int R )
{
  Node l, r;
  Split(t, t, r, R + 1);
  Split(t, l, t, L); // L = 0
  
  t->is_reversed ^= 1;

  Merge(t, l, t);
  Merge(t, t, r);
}


int main()
{
  //            1  2   3  4
  int a[] = {1, 9, 2, -2, 7, 3, 5};
  int n = sizeof(a) / sizeof(a[0]);
  forn(i, n)
    InsertFast(root, i, a[i], R());
  root->out_array(), puts("");
  Reverse(root, 1, 4);
  root->out_array(), puts("");
  //printf("sum = %I64d\n", Sum(root, 1, 4));
  return 0;
}