const int maxt = (int)1e7;

struct tree
{
  int l, r;
};

tree t[maxt];
int tpos = 0;

int NewT( int l, int r )
{
  assert(tpos < maxt);
  t[tpos].l = l;
  t[tpos].r = r;
  return tpos++;
}

struct PArray // Persistent Array
{
  int n, root;

  int Build( int n, int *a )
  {
    if (n == 1)
      return NewT(*a, *a);
    int m = n / 2;
    return NewT(Build(m, a), Build(n - m, a + m));
  }
  
  PArray( int _n, int *a ) : n(_n), root(Build(n, a)) { }
  PArray( int _n, int _root ) : n(_n), root(_root) { }
  PArray() { }

  int Get( int v, int n, int k )
  {
    if (n == 1)
      return t[v].l;
    int m = n / 2;
    return k < m ? Get(t[v].l, m, k) : Get(t[v].r, n - m, k - m);
  }

  int operator [] ( int i )
  {
    return Get(root, n, i);
  }

  int Change( int v, int n, int i, int x )
  {
    if (i < 0 || i >= n)
      return v;
    if (n == 1)
      return NewT(x, x);
    int m = n / 2;
    return NewT(Change(t[v].l, m, i, x), Change(t[v].r, n - m, i - m, x));
  }

  PArray Change( int i, int x )
  {
    return PArray(n, Change(root, n, i, x));
  }
};