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 d = IntArray(n + 1) { 0 }
	
	fun apply(coef: Int) {	
		var qs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
		for (i in 0 until n) {
			qs[0].add(Pair(i, n + 1))
		}
		
		var len = n + 1
		while (true) {
			val posq = IntArray(n) { -1 }
			val poss = IntArray(n) { -1 }
			val sv = IntArray(n) { -1 }
			val fq = BIT(n)
			val fs = BIT(n)
			
			var cntq = 0
			var cnts = 0
			val nqs = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList<Pair<Int, Int>>() }
			var j = 0
			
			var last = true
			for (l in 0 until n + 1) {
				for (it in qs[l]) {
					val i = it.first
					val r = it.second
					if (r - l == 1) {
						d[l] += coef
						continue
					}
					
					last = false
					val m = (l + r) / 2
					while (j < m) {
						val x = q[j].x
						if (q[j].t == 1) {
							posq[x] = cntq
							sv[x] = cnts
							cntq += 1
							cnts += 1
							fq.upd_pr(posq[x], a[x])
						}
						else if (q[j].t == 2){
							poss[x] = cnts
							cnts += 1
							fs.upd_su(poss[x], a[x])
						}
						else{
							fq.upd_pr(posq[x], -a[x])
							posq[x] = -1
							poss[x] = sv[x]
							fs.upd_su(poss[x], a[x])
						}
						j += 1
					}
					assert(j == m)
					if (poss[i] == -1 || posq[i] == -1) {
						nqs[m].add(Pair(i, r))
						continue
					}
					val tq = fq.get_pr(posq[i] - 1)
					val ts = fs.get_su(poss[i] + 1)
					var ok = true
					if (coef == 1) {
						ok = tq - a[i] >= ts
					}
					else {
						ok = tq + a[i] > ts
					}
					if (ok) {
						nqs[m].add(Pair(i, r))
					}
					else {
						nqs[l].add(Pair(i, m))
					}
				}
			}
			qs = nqs
			if (last) {
				break
			}
		}
		println("")
	}
	
	apply(1)
	apply(-1)
	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"))
}

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"))
}