← 返回题目列表

Codeforces · 1919/C

C. 分组增加

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

给定一个数组 $$$a$$$,大小为 $$$n$$$。您将执行以下过程来计算罚款:

1. 将数组 $$$a$$$ 拆分为两个(可能为空)子序列$$$^\dagger$$$ $$$s$$$ 和 $$$t$$$,使得 $$$a$$$ 的每个元素都在 $$$s$$$ 或 $$$t^\ddagger$$$ 中。
2. 对于大小为 $$$m$$$ 的数组 $$$b$$$,将数组 $$$b$$$ 的惩罚 $$$p(b)$$$ 定义为 $$$1$$$ 和 $$$m - 1$$$ 之间的索引 $$$i$$$ 的数量,其中 $$$b_i < b_{i + 1}$$$。
3. 您将收到的总罚款为 $$$p(s) + p(t)$$$。

如果您以最佳方式执行上述过程,请找出您将受到的最小可能惩罚。

$$$^\dagger$$$ 序列 $$$x$$$ 是序列 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得。

$$$^\ddagger$$$ 将数组 $$$a=[3,1,4,1,5]$$$ 拆分为 $$$(s,t)$$$ 的一些有效方法是 $$$([3,4,1,5],[1])$$$、$$$([1,1],[3,4,5])$$$ 和$$$([\,],[3,1,4,1,5])$$$ 而一些无效的分割 $$$a$$$ 的方法是 $$$([3,4,5],[1])$$$, $$$([3,1,4,1],[1,5])$$$ 和 $$$([1,3,4],[5,1])$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示您将收到的最小可能惩罚。

示例

输入 #1

5
5
1 2 3 4 5
8
8 2 3 1 1 7 4 3
5
3 3 3 3 3
1
1
2
2 1

输出 #1

3
1
0
0
0

注意

在第一个测试用例中,分割 $$$a$$$ 的可能方法是 $$$s=[2,4,5]$$$ 和 $$$t=[1,3]$$$。惩罚是$$$p(s)+p(t)=2 + 1 =3$$$。

在第二个测试用例中,分割 $$$a$$$ 的可能方法是 $$$s=[8,3,1]$$$ 和 $$$t=[2,1,7,4,3]$$$。惩罚是$$$p(s)+p(t)=0 + 1 =1$$$。

在第三个测试用例中,分割 $$$a$$$ 的可能方法是 $$$s=[\,]$$$ 和 $$$t=[3,3,3,3,3]$$$。惩罚是$$$p(s)+p(t)=0 + 0 =0$$$。