← 返回题目列表

Codeforces · 1385/C

C. 做好事

中文机器翻译题面 查看原题

给定一个由 $$$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]$$$。结果数组很好。可以证明,如果删除较少数量的第一个元素,结果不会很好。