trait PriorityQueue[T] {
  // Pre: true. Post: Q' is the empty multiset.
  def clear(): Unit

  // Pre: true. Post: Q' = Q with one additional occurrence of x.
  def insert(x: T): Unit

  // Pre: Q is nonempty.
  // Post: result is a minimum of Q;
  //       Q' is Q with exactly one occurrence of result removed.
  def delMin(): T

  // Pre: true. Post: result iff Q is empty, and Q' = Q.
  def isEmpty(): Boolean
}

def solve(puzzle: Flip): Flip = {
  val pending = scala.collection.mutable.Queue[Flip]()
  pending.enqueue(puzzle)
  while (!pending.isEmpty) {
    val current = pending.dequeue()
    if (current.isIdentity) return current
    var k = 2L
    while (k <= current.game.length.toLong) {
      pending.enqueue(current.flip(k.toInt))
      k += 1L
    }
  }
  throw new IllegalStateException("No solution")
}

val puzzle = new Flip(n)
println("Solving:")
println(puzzle)
val answer = solve(puzzle)
println("Solved:")
println(answer)

override def toString: String =
  game.mkString("[", ", ", "]") +
    "    history of flips: " + flips.reverse.toString

def flip(k: Int): Flip = {
  require(1 < k && k <= game.length)
  val result = new Flip(game.length)
  var i = 0
  while (i < game.length) {
    val source = if (i < k) k - 1 - i else i
    result.game(i) = game(source)
    i += 1
  }
  result.flips = k :: flips
  result
}

def isIdentity: Boolean = {
  var i = 0
  while (i < game.length && game(i) == i) {
    i += 1
  }
  i == game.length
}

class BitMapSet(val MAXVALUE: Int) extends IntSet {
  require(MAXVALUE >= 0)
  private val bits = Array.fill(MAXVALUE)(false)
  private var count = 0

  def contains(elem: Int): Boolean =
    0 <= elem && elem < MAXVALUE && bits(elem)

  def add(elem: Int): Boolean = {
    require(0 <= elem && elem < MAXVALUE, "Outside bitmap universe")
    if (bits(elem)) false
    else {
      bits(elem) = true
      count += 1
      true
    }
  }

  def size: Int = count
}

// add(elem):
//   S' = S0 union {elem}
//   result == !S0.contains(elem)

// contains(elem):
//   S' = S0
//   result == S0.contains(elem)

// size:
//   S' = S0
//   result == cardinality(S0)

def selectIterative(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  var low = l
  var high = r
  var rank = k
  while (high - low > 1) {
    val p = partition(low, high)
    val pivotRank = p - low
    if (rank == pivotRank) return a(p)
    if (rank < pivotRank) high = p
    else {
      rank -= pivotRank + 1
      low = p + 1
    }
  }
  a(low)
}

def select(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  if (r - l == 1) a(l)
  else {
    val p = partition(l, r)
    val rank = p - l
    if (k == rank) a(p)
    else if (k < rank) select(k, l, p)
    else select(k - rank - 1, p + 1, r)
  }
}

def partition(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  def swap(i: Int, j: Int): Unit = {
    val t = a(i); a(i) = a(j); a(j) = t
  }
  val chosen = bestIndex(l, r)
  val x = a(chosen)
  swap(chosen, r - 1)
  var p = l
  var j = l
  while (j < r - 1) {
    if (a(j) < x) {
      swap(p, j)
      p += 1
    }
    j += 1
  }
  swap(p, r - 1)
  p
}

def bestIndex(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  val first = l
  val middle = l + (r - l) / 2
  val last = r - 1
  if (a(first) <= a(middle)) {
    if (a(middle) <= a(last)) middle
    else if (a(first) <= a(last)) last
    else first
  } else {
    if (a(first) <= a(last)) first
    else if (a(middle) <= a(last)) last
    else middle
  }
}