#include <iostream>
#include <chrono>
#include <random>
#include <cassert>

using namespace std;

class Sequence
{
public:
  Sequence(int n) : m_rbTree(n)
  {
    for (int i = 0; i < n; ++i)
    {
      m_rbTree.insert(i);
    }
  }

  int get(int i) const
  {
    assert(i >= 0 && i < size() && "Index out of range.");
    return m_rbTree.get(i);
  }

  void erase(int i)
  {
    assert(i >= 0 && i < size() && "Index out of range.");
    m_rbTree.erase(i);
  }

  int size() const
  {
    return m_rbTree.size();
  }

private:

  class RedBlackTree
  {
  public:
    RedBlackTree(size_t nodesCount)
      : m_pool(nodesCount + 1)
    {
      void* ptr = m_pool.allocate();
      m_nil = new(ptr)Node();
      m_root = m_nil;

      m_nil->parent     = nullptr;
      m_nil->leftChild  = nullptr;
      m_nil->rightChild = nullptr;
      m_nil->key        = -1;
      m_nil->size       =  0;
      m_nil->color      = Color::BLACK;
    }

    void insert(int key)
    {
      void* ptr = m_pool.allocate();
      Node* node = new(ptr)Node(key);
      insert(node);
    }

    int get(int i) const
    {
      Node* n = select(m_root, i + 1);
      return n->key;
    }

    void erase(int i)
    {
      Node* n = select(m_root, i + 1);
      remove(n);
    }

    int size() const
    {
      return m_root->size;
    }

  private:
    enum class Color : uint8_t { RED, BLACK };

    struct Node
    {
      Node() = default;
      Node(int key_) : key(key_) {}

      Node* parent;
      Node* leftChild;
      Node* rightChild;
      int   key;
      int   size;
      Color color;
    };

    class MemoryPool
    {
    public:
      MemoryPool(size_t nodesCount)
        : m_memory(new Node[nodesCount])
        , m_currentFreeNode(m_memory)
      {}

      ~MemoryPool()
      {
        delete[] m_memory;
      }

      Node* allocate()
      {
        auto result = m_currentFreeNode;
        ++m_currentFreeNode;
        return result;
      }

    private:
      Node* m_memory;
      Node* m_currentFreeNode;
    };

  private:
    Node* select(Node* x, int i) const
    {
      int r = x->leftChild->size + 1;

      if (i == r)
        return x;
      else if (i < r)
        return select(x->leftChild , i);
      else
        return select(x->rightChild, i - r);
    }

    void insert(Node* z)
    {
      Node* y = m_nil;
      Node* x = m_root;

      while (x != m_nil)
      {
        ++x->size;
        y = x;
        if (z->key < x->key)
          x = x->leftChild;
        else
          x = x->rightChild;
      }

      z->parent = y;

      if (y == m_nil)
        m_root = z;
      else if (z->key < y->key)
        y->leftChild  = z;
      else
        y->rightChild = z;

      z->leftChild  = m_nil;
      z->rightChild = m_nil;
      z->size       = 1;
      z->color      = Color::RED;

      insertFixup(z);
    }

    void insertFixup(Node* z)
    {
      assert(z);
      assert(z->parent);

      while (z->parent->color == Color::RED)
      {
        assert(z->parent->parent);

        if (z->parent == z->parent->parent->leftChild)
        {
          Node* y = z->parent->parent->rightChild;
          assert(y);

          if (y->color == Color::RED)
          {
            z->parent->color = Color::BLACK;
            y->color = Color::BLACK;
            z->parent->parent->color = Color::RED;
            z = z->parent->parent;
          }
          else
          {
            if (z == z->parent->rightChild)
            {
              z = z->parent;
              leftRotate(z);
            }
            z->parent->color = Color::BLACK;
            z->parent->parent->color = Color::RED;
            rightRotate(z->parent->parent);
          }
        }
        else
        {
          Node* y = z->parent->parent->leftChild;
          assert(y);

          if (y->color == Color::RED)
          {
            z->parent->color = Color::BLACK;
            y->color = Color::BLACK;
            z->parent->parent->color = Color::RED;
            z = z->parent->parent;
          }
          else
          {
            if (z == z->parent->leftChild)
            {
              z = z->parent;
              rightRotate(z);
            }
            z->parent->color = Color::BLACK;
            z->parent->parent->color = Color::RED;
            leftRotate(z->parent->parent);
          }
        }
      }

      m_root->color = Color::BLACK;
    }

    void remove(Node* z)
    {
      assert(z);
      assert(z != m_nil);

      Node* x;
      Node* y = z;
      Color yOriginalColor = y->color;

      // decrement sizes on path to the root
      while (y != m_nil)
      {
        --y->size;
        y = y->parent;
      }

      if (z->leftChild == m_nil)
      {
        x = z->rightChild;
        transplant(z, z->rightChild);
      }
      else if (z->rightChild == m_nil)
      {
        x = z->leftChild;
        transplant(z, z->leftChild);
      }
      else
      {
        y = findMinimum(z->rightChild);
        yOriginalColor = y->color;
        x = y->rightChild;

        if (y->parent == z)
        {
          x->parent = y;
        }
        else
        {
          transplant(y, y->rightChild);
          y->rightChild = z->rightChild;
          y->rightChild->parent = y;

          Node* temp = x->parent;
          while (temp != y)
          {
            --temp->size;
            temp = temp->parent;
          }

          y->size = y->leftChild->size + 1;
        }

        transplant(z, y);
        y->leftChild = z->leftChild;
        y->leftChild->parent = y;
        y->color = z->color;
        y->size = y->leftChild->size + y->rightChild->size + 1;
      }

      if (yOriginalColor == Color::BLACK)
      {
        removeFixup(x);
      }
    }

    void removeFixup(Node* x)
    {
      assert(x);

      while (x != m_root && x->color == Color::BLACK)
      {
        if (x == x->parent->leftChild)
        {
          Node* w = x->parent->rightChild;

          assert(w);
          assert(w != m_nil);

          if (w->color == Color::RED)
          {
            w->color = Color::BLACK;
            x->parent->color = Color::RED;
            leftRotate(x->parent);
            w = x->parent->rightChild;
          }

          if (w->leftChild->color  == Color::BLACK &&
              w->rightChild->color == Color::BLACK)
          {
            w->color = Color::RED;
            x = x->parent;
          }
          else
          {
            if (w->rightChild->color == Color::BLACK)
            {
              w->leftChild->color = Color::BLACK;
              w->color = Color::RED;
              rightRotate(w);
              w = x->parent->rightChild;
            }

            w->color = x->parent->color;
            x->parent->color = Color::BLACK;
            w->rightChild->color = Color::BLACK;
            leftRotate(x->parent);
            x = m_root;
          }
        }
        else
        {
          Node* w = x->parent->leftChild;

          assert(w);
          assert(w != m_nil);

          if (w->color == Color::RED)
          {
            w->color = Color::BLACK;
            x->parent->color = Color::RED;
            rightRotate(x->parent);
            w = x->parent->leftChild;
          }

          if (w->leftChild->color  == Color::BLACK &&
              w->rightChild->color == Color::BLACK)
          {
            w->color = Color::RED;
            x = x->parent;
          }
          else
          {
            if (w->leftChild->color == Color::BLACK)
            {
              w->rightChild->color = Color::BLACK;
              w->color = Color::RED;
              leftRotate(w);
              w = x->parent->leftChild;
            }

            w->color = x->parent->color;
            x->parent->color = Color::BLACK;
            w->leftChild->color = Color::BLACK;
            rightRotate(x->parent);
            x = m_root;
          }
        }
      }

      x->color = Color::BLACK;
    }

    void leftRotate(Node* x)
    {
      assert(x);

      Node* y = x->rightChild;
      x->rightChild = y->leftChild;

      if (y->leftChild != m_nil)
        y->leftChild->parent = x;

      y->parent = x->parent;

      if (x->parent == m_nil)
        m_root = y;
      else if (x == x->parent->leftChild)
        x->parent->leftChild  = y;
      else
        x->parent->rightChild = y;

      y->leftChild = x;
      x->parent = y;
      y->size = x->size;
      x->size = x->leftChild->size + x->rightChild->size + 1;
    }

    void rightRotate(Node* x)
    {
      assert(x);

      Node* y = x->leftChild;
      x->leftChild = y->rightChild;

      if (y->rightChild != m_nil)
        y->rightChild->parent = x;

      y->parent = x->parent;

      if (x->parent == m_nil)
        m_root = y;
      else if (x == x->parent->rightChild)
        x->parent->rightChild = y;
      else
        x->parent->leftChild  = y;

      y->rightChild = x;
      x->parent = y;
      y->size = x->size;
      x->size = x->leftChild->size +x->rightChild->size + 1;
    }

    void transplant(Node* u, Node* v)
    {
      if (u->parent == m_nil)
        m_root = v;
      else if (u == u->parent->leftChild)
        u->parent->leftChild  = v;
      else
        u->parent->rightChild = v;

      v->parent = u->parent;
    }

    Node* findMinimum(Node* x) const
    {
      assert(x);
      assert(x != m_nil);

      while (x->leftChild != m_nil)
        x = x->leftChild;

      return x;
    }

  private:
    MemoryPool m_pool;
    Node* m_nil;
    Node* m_root;

  }; // RedBlackTree class

private:
  RedBlackTree m_rbTree;

}; // Sequence class


#ifdef __PRETTY_FUNCTION__
  #define TEST_ASSERT(condition)                                           \
    if (!(condition)) {                                                    \
      std::cerr << "Assertion failed at " << __FILE__ << ":" << __LINE__;  \
      std::cerr << " inside '" << __PRETTY_FUNCTION__ << "'" <<std::endl;  \
      std::cerr << "Condition: " << #condition << std::endl;               \
      abort();                                                             \
    }
#else
  #define TEST_ASSERT(condition)                                           \
    if (!(condition)) {                                                    \
      std::cerr << "Assertion failed at " << __FILE__ << ":" << __LINE__;  \
      std::cerr << "Condition: " << #condition << std::endl;               \
      abort();                                                             \
    }
#endif

void test1()
{
  Sequence s(10);
  for (int i = 0; i < 10; ++i)
  {
    TEST_ASSERT(s.get(i) == i);
  }
}

void test2()
{
  Sequence s(10);
  s.erase(0);
  s.erase(0);
  s.erase(0);
  for (int i = 0; i < 7; ++i)
  {
    TEST_ASSERT(s.get(i) == i + 3);
  }
}

void test3()
{
  Sequence s(10);
  s.erase(9);
  s.erase(0);
  s.erase(7);
  s.erase(0);
  for (int i = 0; i < 6; ++i)
  {
    TEST_ASSERT(s.get(i) == i + 2);
  }
}

void test4()
{
  Sequence s(10);
  s.erase(9);
  s.erase(5);
  s.erase(7);
  s.erase(2);
  s.erase(0);
  s.erase(0);
  s.erase(0);
  s.erase(0);
  s.erase(1);
  TEST_ASSERT(s.get(0) == 6);
}

void test5()
{
  Sequence s(10);
  s.erase(5);
  TEST_ASSERT(s.get(5) == 6);
  s.erase(8);
  s.erase(0);
  TEST_ASSERT(s.get(5) == 7);
  s.erase(3);
  TEST_ASSERT(s.get(3) == 6);
  s.erase(4);
  TEST_ASSERT(s.get(0) == 1);
  TEST_ASSERT(s.get(1) == 2);
  TEST_ASSERT(s.get(2) == 3);
  TEST_ASSERT(s.get(3) == 6);
  TEST_ASSERT(s.get(4) == 8);
}

void test6()
{
  Sequence s(3);
  s.erase(1);
  TEST_ASSERT(s.get(0) == 0);
  TEST_ASSERT(s.get(1) == 2);
  s.erase(1);
  TEST_ASSERT(s.get(0) == 0);
  s.erase(0);
}

void eraseAlwaysZeroIndexTest()
{
  static constexpr int SIZE = 10'000'000;

  cout << "Starting eraseAlwaysZeroIndexTest with " << SIZE << " elements ..." << endl;

  auto timeBegin = chrono::high_resolution_clock::now();

  Sequence s(SIZE);
  for (int i = 0; i < SIZE; ++i)
  {
    s.erase(0);
  }

  auto timeEnd = chrono::high_resolution_clock::now();

  cout << "eraseAlwaysZeroIndexTest(): "
       << chrono::duration_cast<chrono::milliseconds>(
            timeEnd - timeBegin).count() << " ms." << endl;
}

void eraseAlwaysLastIndexTest()
{
  static constexpr int SIZE = 10'000'000;

  cout << "Starting eraseAlwaysLastIndexTest with " << SIZE << " elements ..." << endl;

  auto timeBegin = chrono::high_resolution_clock::now();

  Sequence s(SIZE);
  for (int i = 0; i < SIZE; ++i)
  {
    s.erase(SIZE - i - 1);
  }

  auto timeEnd = chrono::high_resolution_clock::now();

  cout << "eraseAlwaysLastIndexTest(): "
       << chrono::duration_cast<chrono::milliseconds>(
            timeEnd - timeBegin).count() << " ms." << endl;
}

void eraseRandomIndexTest()
{
  static constexpr int SIZE = 10'000'000;

  cout << "Starting eraseRandomIndexTest with " << SIZE << " elements ..." << endl;

  auto timeBegin = chrono::high_resolution_clock::now();

  random_device rd;
  mt19937 gen(rd());

  Sequence s(SIZE);
  for (int i = 0; i < SIZE; ++i)
  {
    uniform_int_distribution<> distribution(0, SIZE - i - 1);
    s.erase(distribution(gen));
  }

  auto timeEnd = chrono::high_resolution_clock::now();

  cout << "eraseRandomIndexTest(): "
       << chrono::duration_cast<chrono::milliseconds>(
            timeEnd - timeBegin).count() << " ms." << endl;
}

class ArraySequence
{
public:
  ArraySequence(int n)
    : m_size(n)
    , m_data(new int[m_size])
  {
    for (int i = 0; i < m_size; ++i)
    {
      m_data[i] = i;
    }
  }

  ~ArraySequence()
  {
    delete[] m_data;
  }

  int get(int i) const
  {
    assert(i >= 0 && i < m_size && "Index out of range.");
    return m_data[i];
  }

  void erase(int i)
  {
    assert(i >= 0 && i < m_size && "Index out of range.");
    --m_size;
    for (int j = i; j < m_size; ++j)
    {
      m_data[j] = m_data[j + 1];
    }
  }

  int size() const
  {
    return m_size;
  }

private:
  int  m_size;
  int* m_data;
};


void correctnessTest()
{
  static constexpr int SIZE = 10'000;

  cout << "Starting correctness test with " << SIZE << " elements ..." << endl;

  ArraySequence arraySequence(SIZE);
  Sequence rbtSequence(SIZE);

  random_device rd;
  mt19937 gen(rd());

  for (int i = 0; i < SIZE; ++i)
  {
    uniform_int_distribution<> distribution(0, SIZE - i - 1);

    int index = distribution(gen);
    arraySequence.erase(index);
    rbtSequence.erase(index);

    TEST_ASSERT(arraySequence.size() == rbtSequence.size());
    for (int j = 0; j < arraySequence.size(); ++j)
    {
      TEST_ASSERT(arraySequence.get(j) == rbtSequence.get(j));
    }
  }

  cout << "Correctness test passed." << endl;
}

int main()
{
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();

  correctnessTest();

  eraseAlwaysZeroIndexTest();
  eraseAlwaysLastIndexTest();
  eraseRandomIndexTest();

  return 0;
}