fun main() = repeat(readln().toInt()) {
  readln().toInt()
  val a = readln().split(" ").map { it.toInt() }
  println(if (a.dropLast(1).contains(a.last() - 1)) a.last() - 1 else "Ambiguous")
}

fun main() = repeat(readln().toInt()) {
  val n = readln().toInt()
  println((listOf(1) + (n downTo 2)).joinToString(" "))
}

fun main() = repeat(readln().toInt()) {
  val a = readln().split("+")
  val ans = a.foldIndexed(0L) { i, res, s ->
    res + if (i == 0 || i == a.size - 1)
      s.toLong()
    else 
      (1 until s.length).maxOf { s.take(it).toLong() + s.drop(it).toLong() }
  }
  println(ans)
}

fun main() {
    repeat(readln().toInt()) {
        val (n, h, b) = readln().split(' ').map { it.toLong() }
        val grid = Array(2) { readln() }
        val sheepColumn = grid[0].indices.find { grid[0][it] == 'S' || grid[1][it] == 'S' }!!
        val wolvesLeft = (0..1).sumOf { grid[it].take(sheepColumn).count { it == 'W' } }
        val wolvesRight = (0..1).sumOf { grid[it].substring(sheepColumn).count { it == 'W' } }

        val ans = minOf(
            (wolvesLeft + wolvesRight) * h,
            wolvesLeft * h + 2 * b,
            wolvesRight * h + 2 * b,
            3 * b
        )
        println(ans)
    }
}

const val INF = 1e9.toInt()
const val vars = "RPS"

fun main() = repeat(readln().toInt()) {  
  val a = readln().map { vars.indexOf(it) }
  
  fun calc(a : List<Int>) : Int {
    if (a[0] != 0) return INF
    val balance = a.zipWithNext().fold(0) { s, (x, y) ->
      s + (if (x == y) 1 else 0) - (if ((x + 2) % 3 == y) 1 else 0)
    }
    return a.size + maxOf(balance, 0)
  }
  
  println(minOf(
    calc(a),
    calc(listOf(0) + a),
    calc(listOf(0, 2) + a)
   ))
}

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val a = readln().split(" ").map { it.toInt() - 1 }
  
  val prev = IntArray(n + 1) { -1 }
  val pos = IntArray(n) { -1 } 
  
  for (i in 0 until n) {
    for (j in a[i]-1..a[i]+1) {
      if (0 <= j && j < n) {
        prev[i] = maxOf(prev[i], pos[j])
      }
    }
    pos[a[i]] = i
  }
  
  val st = mutableListOf(n)
  var ans = 0L
  for (i in (n - 1) downTo 0) {
    while (st.size > 0 && prev[st.last()] >= i) {
      st.removeLast()
    }
    ans += st.last() - i
    st.add(i)
  }
  
  println(ans)
}

const val LOG = 19

fun main() = repeat(readln().toInt()) {  
  val n = readln().toInt()
  val p = readln().split(" ").map { it.toInt() - 1 }
  val ans = IntArray(n - 1) { n }
  
  fun rec(step: Int, p: List<Int>) {
    if (p.size == 1 || step == LOG) return
    for (cur in listOf(p, p.reversed())) {
      val (a, b) = cur.zipWithNext().partition { (x, y) -> x < y }
      a.forEach { (x, _) -> ans[x] = minOf(ans[x], step) }
      rec(step + 1, b.map { (x, _) -> x} + cur.last())
    }
  }
  
  rec(1, p)
  
  println(ans.joinToString(" "))
}

const val INF = 1e9.toInt()
const val B = 5

fun main() = repeat(readln().toInt()) {
  val (n, m, k) = readInts()
  val a = Array(n) { readInts() }
  
  var ans = 0
  
  for (bit in 0 until B) {
    val g = Array(n) { ArrayList<Pair<Int, Int>>() }
    for (i in 0 until n) {
      for (j in 0 until i) {
        val cnt = IntArray(4) { 0 }
        for (x in 0 until m) {
          val f = (a[i][x] shr bit) and 1
          val s = (a[j][x] shr bit) and 1
          ++cnt[f * 2 + s];
        }
        val f1 = (cnt[0] < k && cnt[3] < k)
        val f2 = (cnt[1] < k && cnt[2] < k)
        if (f1 != f2) {
          g[i].add(j to if (f2) 1 else 0)
          g[j].add(i to if (f2) 1 else 0)
        } else if (!f1) {
          return@repeat println("-1")
        }
      }
    }
    
    val color = IntArray(n) { -1 }
    val cnt = IntArray(2) { 0 }
    var ok = true
    
    fun dfs(v: Int, c: Int) {
      color[v] = c
      ++cnt[c]
      for ((u, d) in g[v]) {
        if (color[u] != -1) {
          if ((c xor d) != color[u]) {
            ok = false
          }
        } else {
          dfs(u, c xor d)
        }
      }
    }
    
    for (v in 0 until n) {
      if (color[v] != -1) continue
      cnt.fill(0)
      dfs(v, 0)
      if (!ok) return@repeat println("-1")
      ans += cnt.min() shl bit
    }
  }
  
  println(maxOf(0, ans))
}

fun readInts() = readln().split(" ").map { it.toInt() }

class Query(val t: Int, val x: Int)

class BIT(val mx: Int) {
	val f = LongArray(mx) { 0L }
	
	fun upd_pr(pos: Int, x: Int) {
		var i = pos
		while (i < mx) {
			f[i] = f[i] + x
			i = i or (i + 1)
		}
	}

	fun get_pr(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i >= 0) {
			res += f[i]
			i = (i and (i + 1)) - 1
		}
		return res
	}

	fun upd_su(pos: Int, x: Int) {
		var i = pos
		while (i >= 0) {
			f[i] = f[i] + x
			i = (i and (i + 1)) - 1
		}
	}

	fun get_su(pos: Int) : Long {
		var res = 0L
		var i = pos
		while (i < mx) {
			res += f[i]
			i = i or (i + 1)
		}
		return res
	}
}

fun main() {
	val n = readLine()!!.toInt()
	val a = readLine()!!.split(" ").map { it.toInt() }
	val q = Array(n) { Query(-1, -1) }
	for (i in 0 until n) {
		val (t, x) = readLine()!!.split(" ").map { it.toInt() }
		q[i] = Query(t, x - 1)
	}
	val fq = BIT(n)
	val fs = BIT(n)
	
	val d = IntArray(n + 1) { 0 }
	val posq = IntArray(n) { -1 }
	val poss = IntArray(n) { -1 }
	val sv = IntArray(n) { -1 }
	var cntq = 0
	var cnts = 0
	
	fun calc(l: Int, r: Int, coef: Int, all: ArrayList<Int>) {
		if (l == r - 1) {
			d[l] += all.size * coef
			return
		}
		
		val m = (l + r) / 2
		
		val who_chg = ArrayList<Int>()
		val idx_chg = ArrayList<Int>()
		val val_chg = ArrayList<Int>()
		val chq = ArrayList<Pair<Int, Int>>()
		val chs = ArrayList<Pair<Int, Int>>()
		
		for (i in l until m) {
			val x = q[i].x
			if (q[i].t == 1) {
				who_chg.add(0)
				idx_chg.add(x)
				val_chg.add(posq[x])
				posq[x] = cntq
				who_chg.add(2)
				idx_chg.add(x)
				val_chg.add(sv[x])
				sv[x] = cnts
				cntq += 1
				cnts += 1
				chq.add(Pair(posq[x], -a[x]))
				fq.upd_pr(posq[x], a[x])
			}
			else if (q[i].t == 2){
				who_chg.add(1)
				idx_chg.add(x)
				val_chg.add(poss[x])
				poss[x] = cnts
				cnts += 1
				chs.add(Pair(poss[x], -a[x]))
				fs.upd_su(poss[x], a[x])
			}
			else{
				chq.add(Pair(posq[x], a[x]))
				fq.upd_pr(posq[x], -a[x])
				who_chg.add(0)
				idx_chg.add(x)
				val_chg.add(posq[x])
				posq[x] = -1
				who_chg.add(1)
				idx_chg.add(x)
				val_chg.add(poss[x])
				poss[x] = sv[x]
				who_chg.add(2)
				idx_chg.add(x)
				val_chg.add(sv[x])
				sv[x] = -1
				chs.add(Pair(poss[x], -a[x]))
				fs.upd_su(poss[x], a[x])
			}
		}
	
		val tol = ArrayList<Int>()
		val tor = ArrayList<Int>()
		
		for (x in all) {
			if (poss[x] == -1 || posq[x] == -1) {
				tor.add(x)
				continue
			}
			val tq = fq.get_pr(posq[x] - 1)
			val ts = fs.get_su(poss[x] + 1)
			var ok = true
			if (coef == 1) {
				ok = tq - a[x] >= ts
			}
			else {
				ok = tq + a[x] > ts
			}
			if (ok) {
				tor.add(x)
			}
			else {
				tol.add(x)
			}
		}
	
		calc(m, r, coef, tor)
		
		who_chg.reverse()
		idx_chg.reverse()
		val_chg.reverse()
		
		for (i in 0 until who_chg.size) {
			if (who_chg[i] == 0) {
				posq[idx_chg[i]] = val_chg[i]
			}
			else if (who_chg[i] == 1) {
				poss[idx_chg[i]] = val_chg[i]
			}
			else {
				sv[idx_chg[i]] = val_chg[i]
			}
		}
		
		for (i in l until m) {
			if (q[i].t == 1) {
				cntq -= 1
				cnts -= 1
			}
			else if (q[i].t == 2){
				cnts -= 1
			}
		}

		for (it in chq) {
			fq.upd_pr(it.first, it.second)
		}
		for (it in chs) {
			fs.upd_su(it.first, it.second)
		}
		
		calc(l, m, coef, tol)
	}
	
	val all = ArrayList<Int>()
	for (i in 0 until n) {
		all.add(i)
	}
	calc(0, n + 1, 1, all)
	calc(0, n + 1, -1, all)
	for (i in 0 until n) {
		d[i + 1] += d[i]
	}
	val res = d.map { x -> (if (x == 0) "Yes" else "No") }
	println(res.take(res.size - 1).joinToString(separator = "\n"))
}