给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您必须找到需要从 $$$a$$$ 中删除的元素的最小(最短)前缀的长度,以使其成为一个好的数组。回想一下,数组 $$$a=[a_1, a_2, \dots, a_n]$$$ 的前缀是由几个第一个元素组成的子数组:长度 $$$k$$$ 的数组 $$$a$$$ 的前缀是数组 $$$[a_1, a_2, \dots, a_k]$$$ ($$$0 \le k \le n$$$)。
长度为 $$$m$$$ 的数组 $$$b$$$ 被称为好数组,如果你能从中获得一个非递减数组 $$$c$$$ ($$$c_1 \le c_2 \le \dots \le c_{m}$$$),重复以下操作 $$$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_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,打印答案:需要从 $$$a$$$ 中删除的元素的最短前缀的长度,以使其成为一个好的数组。
示例
输入 #1
5 4 1 2 3 4 7 4 3 3 8 4 5 2 3 1 1 1 7 1 3 1 4 5 3 2 5 5 4 3 2 3
输出 #1
0 4 0 2 3
注意
在示例的第一个测试用例中,数组 $$$a$$$ 已经很好,因此我们不需要删除任何前缀。
在示例的第二个测试用例中,初始数组 $$$a$$$ 不好。让我们删除 $$$a$$$ 的前 $$$4$$$ 个元素,结果是 $$$[4, 5, 2]$$$。结果数组很好。可以证明,如果删除较少数量的第一个元素,结果不会很好。