StandingOvation.scala

import java.io.{FileInputStream, FileOutputStream}

import scala.io.StdIn

object Main extends App {
  Console.setIn(new FileInputStream("A-large.in"))
  Console.setOut(new FileOutputStream("A-large.out"))

  def solve(audiences: String): Int = {

    def getFakeMensCount(audiences: String, shymens: Int = 0, fakeMens: Int = 0, total: Int): Int = {
      if (audiences.isEmpty || shymens > total) {
        fakeMens
      } else {
        val shymen = audiences.head.toString.toInt
        val level = total - audiences.length
        val fakeMen = if (shymens > level) 0 else level - shymens
        getFakeMensCount(audiences.tail, shymens + shymen + fakeMen, fakeMens + fakeMen, total)
      }
    }
    getFakeMensCount(audiences, total = audiences.length)
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { n =>
    val numbers = StdIn.readLine().split(" ")(1)
    println(s"Case #$n: ${solve(numbers)}")
  }
}