CF1385C Make It Good

给定一个由 $n$ 个整数构成的数组 $a$。你需要找出需要从 $a$ 的前缀中删除的最短长度，使得剩下的数组是一个“好数组”。回忆一下，数组 $a=[a_1, a_2, \dots, a_n]$ 的前缀是由前若干个元素组成的子数组：长度为 $k$ 的前缀为 $[a_1, a_2, \dots, a_k]$（$0 \le k \le n$）。 长度为 $m$ 的数组 $b$ 被称为“好数组”，如果你可以通过重复以下操作 $m$ 次，从 $b$ 得到一个非递减数组 $c$（即 $c_1 \le c_2 \le \dots \le c_{m}$）（初始时 $c$ 为空）： - 每次选择 $b$ 的第一个或最后一个元素，从 $b$ 中移除，并将其添加到 $c$ 的末尾。 例如，如果我们依次进行 $4$ 次操作：取 $b_1$，然后取 $b_m$，再取 $b_{m-1}$，最后取 $b_2$，那么 $b$ 变为 $[b_3, b_4, \dots, b_{m-3}]$，$c$ 变为 $[b_1, b_m, b_{m-1}, b_2]$。 举个例子：$b = [1, 2, 3, 4, 4, 2, 1]$。这个数组是好数组，因为我们可以通过如下操作得到非递减数组 $c$： 1. 取 $b$ 的第一个元素，此时 $b = [2, 3, 4, 4, 2, 1]$，$c = [1]$； 2. 取 $b$ 的最后一个元素，此时 $b = [2, 3, 4, 4, 2]$，$c = [1, 1]$； 3. 取 $b$ 的最后一个元素，此时 $b = [2, 3, 4, 4]$，$c = [1, 1, 2]$； 4. 取 $b$ 的第一个元素，此时 $b = [3, 4, 4]$，$c = [1, 1, 2, 2]$； 5. 取 $b$ 的第一个元素，此时 $b = [4, 4]$，$c = [1, 1, 2, 2, 3]$； 6. 取 $b$ 的最后一个元素，此时 $b = [4]$，$c = [1, 1, 2, 2, 3, 4]$； 7. 取 $b$ 的唯一元素，此时 $b = []$，$c = [1, 1, 2, 2, 3, 4, 4]$，此时 $c$ 是非递减的。 注意，只有一个元素的数组一定是好数组。 请输出需要删除的 $a$ 的最短前缀长度，使得剩下的 $a$ 是好数组。注意，所需长度可以为 $0$。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^5$），表示 $a$ 的各个元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每个测试用例，输出一个答案：需要删除的 $a$ 的最短前缀长度，使得剩下的 $a$ 是好数组。

在第一个样例中，数组 $a$ 已经是好数组，因此不需要删除任何前缀。 在第二个样例中，初始数组 $a$ 不是好数组。我们删除前 $4$ 个元素后，得到 $[4, 5, 2]$，此时数组是好数组。你可以证明，如果删除更少的前缀，结果都不是好数组。 由 ChatGPT 4.1 翻译