← 返回题目列表

Codeforces · 2176/A

A. 反转运算

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

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$。在一个操作中,您可以选择一对索引 $$$i, j$$$,使得 $$$1 \le i \lt j \le n$$$, $$$a_i \gt a_j$$$,并从数组中删除索引 $$$j$$$ 处的元素。之后,数组的大小会减少$$$1$$$,而元素的相对顺序不会改变。

确定在最佳应用情况下可以对数组执行的最大操作数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 初始数组的大小。

每个测试用例的第二行包含 $$$n$$$ 自然数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

输出

对于每个测试用例,输出可以对给定数组执行的最大操作数。

示例

输入
复制

5
3
3 2 1
3
1 2 3
3
3 3 3
5
3 1 4 5 2
1
1

输出
复制

2
0
0
2
0

注意

在第一个示例中,我们可以首先选择值对 $$$i = 2$$$, $$$j = 3$$$,其值为 $$$a_2 = 2$$$, $$$a_3 = 1$$$ 并删除 $$$a_3$$$。生成的数组将为 $$$a = [3, 2]$$$。之后,我们可以通过选择 $$$i = 1$$$, $$$j = 2$$$ 对来删除第二个元素。操作总数为$$$2$$$。

在第二、第三和第五示例中,由于没有合适的对,因此无法执行任何操作。

在第四个示例中,我们可以删除第二个和第五个元素。可以证明,这是最优答案,并且没有解决方案可以删除更多元素。