import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;
class main {

static void test_LogNArray() {
  test_LogNArray(1000);
}

static void test_LogNArray(int n) {
  LogNArray<String> l = new LogNArray();
  assertEqualsVerbose(0, l.size());
  for (int i = -1; i < 2; i++) { int _i = i ; assertException(new Runnable() {  public void run() { try {  l.get(_i) ;
} catch (Exception __e) { throw rethrow(__e); } }  public String toString() { return "l.get(_i)"; }}); }
  l.add("hello");
  assertEqualsVerbose(1, l.size());
  assertException(new Runnable() {  public void run() { try {  l.get(-1) ;
} catch (Exception __e) { throw rethrow(__e); } }  public String toString() { return "l.get(-1)"; }});
  assertEqualsVerbose("hello", l.get(0));
  assertException(new Runnable() {  public void run() { try {  l.get(1) ;
} catch (Exception __e) { throw rethrow(__e); } }  public String toString() { return "l.get(1)"; }});
  
  Random random = predictableRandom();
  
  // n random insertions, complete check
  
  List<String> refl = new ArrayList();
  l.clear();
  for (int _repeat_0 = 0; _repeat_0 < n; _repeat_0++)  {
    int i = random(random, l(refl)+1);
    String id = randomID(random);
    print("add " + i + " " + id);
    refl.add(i, id);
    l.add(i, id);
    assertEquals(l(l), l(refl));
  }
  assertEqualsVerbose(l(l), l(refl));
  for (int i = 0; i < l(refl); i++)
    assertEquals(l.get(i), refl.get(i));
    
  // overwriting
  for (int _repeat_1 = 0; _repeat_1 < n; _repeat_1++)  {
    int i = random(random, l(refl));
    String id = randomID(random);
    print("set " + i + " " + id);
    assertEquals(l.set(i, id), refl.set(i, id));
    assertEquals(l(l), l(refl));
  }
    
  // n random deletions, check after each turn
  for (int _repeat_2 = 0; _repeat_2 < n; _repeat_2++)  {
    int i = random(random, l(refl));
    print("remove " + i);
    assertEquals(l.remove(i), refl.remove(i));
    assertEqualsVerbose(l(l), l(refl));
    for (int j = 0; j < l(refl); j++)
      assertEquals(l.get(j), refl.get(j));
  }
  
  System.out.println("LogNArray works (tested up to size " + n + ")! :)");
}

static int l(Collection l) { return l == null ? 0 : l.size(); }
static int l(String s) { return s == null ? 0 : s.length(); }

static <A> A print(A a) { System.out.println(a); return a; }

static int random(Random r, int n) {
  return n <= 0 ? 0 : r.nextInt(n);
}

static void silentException(Throwable e) {}


static <A> A assertEqualsVerbose(Object x, A y) {
  assertEqualsVerbose((String) null, x, y);
  return y;
}

static <A> A assertEqualsVerbose(String msg, Object x, A y) {
  if (!eq(x, y)) {
    

    throw fail((msg != null ? msg + ": " : "") + /*sfu*/(y) + " != " + /*sfu*/(x));
  } else
    print("OK: " + /*sfu*/(x));
  return y;
}


static void assertException(Runnable r) {
  assertFail(r);
}
static RuntimeException rethrow(Throwable t) {
  
  throw t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}

static RuntimeException rethrow(String msg, Throwable t) {
  throw new RuntimeException(msg, t);
}
static Random predictableRandom() {
  return new Random(0);
}
static int randomID_defaultLength = 12;

static String randomID(int length) {
  return makeRandomID(length);
}

static String randomID(Random r, int length) {
  return makeRandomID(r, length);
}

static String randomID() {
  return randomID(randomID_defaultLength);
}

static String randomID(Random r) {
  return randomID(r, randomID_defaultLength);
}
static <A> A assertEquals(Object x, A y) {
  return assertEquals(null, x, y);
}

static <A> A assertEquals(String msg, Object x, A y) {
  if (assertVerbose()) return assertEqualsVerbose(msg, x, y);
  if (!(x == null ? y == null : x.equals(y)))
    throw fail((msg != null ? msg + ": " : "") + y + " != " + x);
  return y;
}


static boolean eq(Object a, Object b) {
  return a == null ? b == null : a == b || b != null && a.equals(b);
}


static RuntimeException fail() { throw new RuntimeException("fail"); }
static RuntimeException fail(Throwable e) { throw asRuntimeException(e); }
static RuntimeException fail(Object msg) { throw new RuntimeException(String.valueOf(msg)); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }

static void assertFail(Runnable r) {
  try {
    r.run();
  } catch (Throwable e) {
    silentException(e);
    return;
  }
  throw fail("No exception thrown!");
}
static String makeRandomID(int length) {
  return makeRandomID(length, defaultRandomGenerator());
}

static String makeRandomID(int length, Random random) {
  char[] id = new char[length];
  for (int i = 0; i < id.length; i++)
    id[i] = (char) ((int) 'a' + random.nextInt(26));
  return new String(id);
}

static String makeRandomID(Random r, int length) {
  return makeRandomID(length, r);
}
static ThreadLocal<Boolean> assertVerbose_value = new ThreadLocal();

static void assertVerbose(boolean b) {
  assertVerbose_value.set(b);
}

static boolean assertVerbose() { return isTrue(assertVerbose_value.get()); }


static String str(Object o) {
  return o == null ? "null" : o.toString();
}

static String str(char[] c) {
  return new String(c);
}
static RuntimeException asRuntimeException(Throwable t) {
  
  return t instanceof RuntimeException ? (RuntimeException) t : new RuntimeException(t);
}
static Random defaultRandomGenerator() {
  return ThreadLocalRandom.current();
}
static boolean isTrue(Object o) {
  if (o instanceof Boolean)
    return ((Boolean) o).booleanValue();
  if (o == null) return false;
  if (o instanceof ThreadLocal)
    return isTrue(((ThreadLocal) o).get());
  throw fail(getClassName(o));
}


static String getClassName(Object o) {
  return o == null ? "null" : o instanceof Class ? ((Class) o).getName() : o.getClass().getName();
}


// see: https://en.wikipedia.org/wiki/Order_statistic_tree
// based on: https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
final static class LogNArray<Value> extends RandomAccessAbstractList<Value> {

 // A symbol table implemented using a left-leaning red-black BST.
 // This is the 2-3 version.
 
  private static final boolean RED   = true;
  private static final boolean BLACK = false;

  private Node<Value> root;     // root of the BST

  // BST helper node data type
  private static class Node<Value> {
      private Value val;         // associated data
      private Node<Value> left, right;  // links to left and right subtrees
      private boolean color = false;     // color of parent link
      private int size;          // subtree count

      public Node(Value val, boolean color, int size) {
          this.val = val;
          this.color = color;
          this.size = size;
      }
  }

  // is node x red; false if x is null ?
  private boolean isRed(Node<Value> x) {
      if (x == null) return false;
      return x.color == RED;
  }

  // number of node in subtree rooted at x; 0 if x is null
  private int size(Node<Value> x) {
      if (x == null) return 0;
      return x.size;
  } 


  public int size() {
      return size(root);
  }

  public boolean isEmpty() {
      return root == null;
  }


  public void add(int idx, Value val) {
    if (idx < 0 || idx > size()) throw new IndexOutOfBoundsException(idx + " / " + size());
    
    root = add(root, idx, val);
    root.color = BLACK;
    
  }

  // insert the value pair in index k of subtree rooted at h
  private Node<Value> add(Node<Value> h, int k, Value val) { 
    if (h == null) return new Node(val, RED, 1);

    int t = size(h.left);
    if (k < t)
      // replace / fit in left child
      h.left = add(h.left, k, val);
    else if (k == t) {
      // move value to right child, replace value
      h.right = add(h.right, 0, h.val);
      h.val = val;
    } else
      // replace / fit in right child
      h.right = add(h.right, k-t-1, val); 

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.size = size(h.left) + size(h.right) + 1;
    
    

    return h;
  }

  public Value remove(int idx) { 
    Value oldValue = get(idx);
    
    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
      root.color = RED;

    root = remove(root, idx);
    if (root != null) root.color = BLACK;
    
    
    
    return oldValue;
  }

  private Node<Value> remove(Node<Value> h, int k) { 
    int t = size(h.left);
    if (k < t) { // remove from left child
      if (!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);
      h.left = remove(h.left, k);
    } else { // remove from center or right child
      if (isRed(h.left)) {
        h = rotateRight(h);
        t = size(h.left);
      }
      if (h.right == null) return null; // drop whole node
      if (!isRed(h.right) && !isRed(h.right.left)) {
        h = moveRedRight(h);
        t = size(h.left);
      }
      if (k == t) { // replace center value with min of right child
        h.val = nodeAtIndex(h.right, 0).val;
        h.right = remove(h.right, 0);
      }
      else h.right = remove(h.right, k-t-1);
    }
    return balance(h);
  }

  // make a left-leaning link lean to the right
  private Node<Value> rotateRight(Node<Value> h) {
      // assert (h != null) && isRed(h.left);
      Node<Value> x = h.left;
      h.left = x.right;
      x.right = h;
      x.color = x.right.color;
      x.right.color = RED;
      x.size = h.size;
      h.size = size(h.left) + size(h.right) + 1;
      return x;
  }

  // make a right-leaning link lean to the left
  private Node<Value> rotateLeft(Node<Value> h) {
      // assert (h != null) && isRed(h.right);
      Node<Value> x = h.right;
      h.right = x.left;
      x.left = h;
      x.color = x.left.color;
      x.left.color = RED;
      x.size = h.size;
      h.size = size(h.left) + size(h.right) + 1;
      return x;
  }

  // flip the colors of a node and its two children
  private void flipColors(Node<Value> h) {
      // h must have opposite color of its two children
      // assert (h != null) && (h.left != null) && (h.right != null);
      // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
      //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
      h.color = !h.color;
      h.left.color = !h.left.color;
      h.right.color = !h.right.color;
  }

  // Assuming that h is red and both h.left and h.left.left
  // are black, make h.left or one of its children red.
  private Node<Value> moveRedLeft(Node<Value> h) {
      // assert (h != null);
      // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

      flipColors(h);
      if (isRed(h.right.left)) { 
          h.right = rotateRight(h.right);
          h = rotateLeft(h);
          flipColors(h);
      }
      return h;
  }

  // Assuming that h is red and both h.right and h.right.left
  // are black, make h.right or one of its children red.
  private Node<Value> moveRedRight(Node<Value> h) {
      // assert (h != null);
      // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
      flipColors(h);
      if (isRed(h.left.left)) { 
          h = rotateRight(h);
          flipColors(h);
      }
      return h;
  }

  // restore red-black tree invariant
  private Node<Value> balance(Node<Value> h) {
      // assert (h != null);

      if (isRed(h.right))                      h = rotateLeft(h);
      if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
      if (isRed(h.left) && isRed(h.right))     flipColors(h);

      h.size = size(h.left) + size(h.right) + 1;
      return h;
  }


  /**
   * Returns the height of the BST (for debugging).
   * @return the height of the BST (a 1-node tree has height 0)
   */
  public int height() {
      return height(root);
  }
  
  private int height(Node<Value> x) {
      if (x == null) return -1;
      return 1 + Math.max(height(x.left), height(x.right));
  }
  
  public Value get(int k) {
    return nodeAtIndex(k).val;
  }

  public Value set(int k, Value val) {
    Node<Value> n = nodeAtIndex(k);
    Value oldValue = n.val;
    n.val = val;
    return oldValue;
  }

  public Node<Value> nodeAtIndex(int k) {
      if (k < 0 || k >= size()) {
          throw new IndexOutOfBoundsException(k + " / " + size());
      }
      return nodeAtIndex(root, k);
  }

  // the key of rank k in the subtree rooted at x
  private Node<Value> nodeAtIndex(Node<Value> x, int k) {
      // assert x != null;
      // assert k >= 0 && k < size(x);
      int t = size(x.left); 
      if      (t > k) return nodeAtIndex(x.left,  k); 
      else if (t < k) return nodeAtIndex(x.right, k-t-1); 
      else            return x; 
  } 
  
  private boolean check() {
      if (!isSizeConsistent()) println("Subtree counts not consistent");
      if (!is23())             println("Not a 2-3 tree");
      if (!isBalanced())       println("Not balanced");
      return isSizeConsistent() && is23() && isBalanced();
  }

  // are the size fields correct?
  private boolean isSizeConsistent() { return isSizeConsistent(root); }
  private boolean isSizeConsistent(Node<Value> x) {
      if (x == null) return true;
      if (x.size != size(x.left) + size(x.right) + 1) return false;
      return isSizeConsistent(x.left) && isSizeConsistent(x.right);
  } 

  // Does the tree have no red right links, and at most one (left)
  // red links in a row on any path?
  private boolean is23() { return is23(root); }
  private boolean is23(Node<Value> x) {
      if (x == null) return true;
      if (isRed(x.right)) return false;
      if (x != root && isRed(x) && isRed(x.left))
          return false;
      return is23(x.left) && is23(x.right);
  } 

  // do all paths from root to leaf have same number of black edges?
  private boolean isBalanced() { 
      int black = 0;     // number of black links on path from root to min
      Node<Value> x = root;
      while (x != null) {
          if (!isRed(x)) black++;
          x = x.left;
      }
      return isBalanced(root, black);
  }

  // does every path from the root to a leaf have the given number of black links?
  private boolean isBalanced(Node<Value> x, int black) {
      if (x == null) return black == 0;
      if (!isRed(x)) black--;
      return isBalanced(x.left, black) && isBalanced(x.right, black);
  }
  
  public void clear() { root = null; }
}

abstract static class RandomAccessAbstractList<A> extends AbstractList<A> implements RandomAccess {
}

static <A> A println(A a) {
  return print(a);
}

}