class FunIter[T](v: T, f: T => T) extends Iter[T] {
  private class Cell(val head: T) {
    lazy val tail: Cell = new Cell(f(head))
  }

  private class Cursor(private var cell: Cell) extends Iter[T] {
    def hasNext: Boolean = true

    def next(): T = {
      val answer = cell.head
      cell = cell.tail
      answer
    }

    def copy(): Iter[T] = new Cursor(cell)
  }

  private val cursor = new Cursor(new Cell(v))

  def hasNext: Boolean = true
  def next(): T = cursor.next()
  def copy(): Iter[T] = cursor.copy()
}

trait RichIter[T] extends Iter[T] {
  def foreach(f: T => Unit): Unit = {
    while (hasNext) f(next())
  }

  def exists(p: T => Boolean): Boolean = {
    while (hasNext) {
      if (p(next())) return true
    }
    false
  }

  def foldLeft[U](x: U)(f: (U, T) => U): U = {
    var result = x
    while (hasNext) result = f(result, next())
    result
  }
}

class DropUntil[T] private (
    p: T => Boolean, iter: Iter[T],
    saved: Option[T], alreadyStarted: Boolean) extends Iter[T] {

  def this(p: T => Boolean, iter: Iter[T]) =
    this(p, iter, None, false)

  private var pending: Option[T] = saved
  private var started: Boolean = alreadyStarted

  private def prepare(): Unit = {
    if (!started) {
      var found = false
      while (!found && iter.hasNext) {
        val x = iter.next()
        if (p(x)) {
          pending = Some(x)
          found = true
        }
      }
      started = true
    }
  }

  def hasNext: Boolean = {
    prepare()
    pending.nonEmpty || iter.hasNext
  }

  def next(): T = {
    prepare()
    pending match {
      case Some(x) => pending = None; x
      case None =>
        if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
        iter.next()
    }
  }

  def copy(): Iter[T] =
    new DropUntil[T](p, iter.copy(), pending, started)
}

0
1

trait CapitalisePlugIn extends Doc {
  abstract override def insert(x: Char, pos: Int): Unit = {
    super.insert(x.toUpper, pos)
  }
}

trait CharTrackPlugIn extends Doc {
  private val counts = Array.fill[Int](26)(0)

  private def lower(x: Char): Boolean = 'a' <= x && x <= 'z'

  abstract override def insert(x: Char, pos: Int): Unit = {
    super.insert(x, pos)
    if (lower(x)) counts(x - 'a') += 1
  }

  abstract override def delete(pos: Int): Char = {
    val old = super.delete(pos)
    if (lower(old)) counts(old - 'a') -= 1
    old
  }

  def getCount(x: Char): Int = {
    assert('a' <= x && x <= 'z')
    counts(x - 'a')
  }
}

class DocImpl extends Doc {
  private var chars: List[Char] = Nil
  private var length: Int = 0

  def size: Int = length

  def insert(x: Char, pos: Int): Unit = {
    require(0 <= pos && pos <= length)
    val parts = chars.splitAt(pos)
    chars = parts._1 ::: (x :: parts._2)
    length += 1
  }

  def delete(pos: Int): Char = {
    require(0 <= pos && pos < length)
    val parts = chars.splitAt(pos)
    val old = parts._2.head
    chars = parts._1 ::: parts._2.tail
    length -= 1
    old
  }

  def read(pos: Int): Char = {
    require(0 <= pos && pos < length)
    chars(pos)
  }
}

Life1, Party, Study, Life
Life2, Sport, Exercise, Research, Party, Study, Life
Life3, Research, Study, Sport, Party, Exercise, Life

I live.
More on study.
More on party.
I live.
More on study.
More on party.
More on research.
More on exercise.
More on sport.
I live.
More on exercise.
More on party.
More on sport.
More on study.
More on research.

f1 in C, 
f1 in C, f2 in B, 
f1 in C, f2 in A, f3 in B, 
f1 in A, f2 in A, f3 in ObjB, f4 in B, 
f1 in ObjC, f2 in A, f3 in B, f4 in ObjC, f5 in C, 

PROCEDURE Get(k: INTEGER): INTEGER;
VAR l, r, m: INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  l := 0; r := len;
  LOOP
    m := Partition(l, r);
    IF k = m THEN RETURN a[m]
    ELSIF k < m THEN r := m
    ELSE l := m+1
    END
  END
END Get;

PROCEDURE Partition(l, r: INTEGER): INTEGER;
VAR pivot, i, j, tmp: INTEGER;
BEGIN
  ASSERT(l < r);
  pivot := a[r-1];
  i := l; j := l;
  WHILE j < r-1 DO
    IF a[j] < pivot THEN
      tmp := a[i]; a[i] := a[j]; a[j] := tmp;
      i := i+1
    END;
    j := j+1
  END;
  tmp := a[i]; a[i] := a[r-1]; a[r-1] := tmp;
  RETURN i
END Partition;

PROCEDURE Add(x: INTEGER);
VAR i: INTEGER;
BEGIN
  ASSERT(len < N);
  i := len;
  WHILE i > 0 DO
    IF u[i-1] <= x THEN EXIT END;
    u[i] := u[i-1];
    i := i-1
  END;
  u[i] := x;
  len := len+1
END Add;

PROCEDURE Get(k: INTEGER): INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  RETURN u[k]
END Get;

PROCEDURE Add(x: INTEGER);
BEGIN
  ASSERT(len < N);
  u[len] := x;
  len := len+1
END Add;

PROCEDURE Sort(a, b: INTEGER; VAR c, d: INTEGER);
VAR x, y, z: INTEGER;
BEGIN
  c := a; d := b;
  WHILE c < d DO
    x := Run(c, d);
    IF x = d THEN RETURN END;
    y := Run(x, d);
    z := y-c;
    Merge(c, x, y, d);
    c := y;
    d := d+z
  END
END Sort;

PROCEDURE Merge(a, b, c, d: INTEGER);
VAR i, j, k: INTEGER;
BEGIN
  i := a; j := b; k := d;
  WHILE (i < b) & (j < c) DO
    IF u[i] <= u[j] THEN
      u[k] := u[i]; i := i+1
    ELSE
      u[k] := u[j]; j := j+1
    END;
    k := k+1
  END;
  WHILE i < b DO
    u[k] := u[i]; i := i+1; k := k+1
  END;
  WHILE j < c DO
    u[k] := u[j]; j := j+1; k := k+1
  END
END Merge;

PROCEDURE Run(a, b: INTEGER): INTEGER;
VAR c: INTEGER;
BEGIN
  IF a = b THEN RETURN b END;
  c := a+1;
  WHILE c < b DO
    IF u[c-1] > u[c] THEN RETURN c END;
    c := c+1
  END;
  RETURN c
END Run;

l := 0; r := n;
WHILE r-l > 1 DO
  m := l + (r-l) DIV 2;
  IF b[l] # b[m] THEN r := m ELSE l := m END
END;
k := l;