CF1676H1 Maximum Crossings (Easy Version)

本题与另一个版本的唯一区别在于，本题中 $n \leq 1000$，且所有测试用例中 $n$ 的总和不超过 $1000$。 有一个终端，由 $n$ 个相等的线段组成，依次编号为 $1$ 到 $n$。有两个这样的终端，上下排列。 给定一个长度为 $n$ 的数组 $a$。对于所有 $i=1,2,\dots,n$，需要从上方终端的第 $i$ 段的某一点，拉一根直线到下方终端的第 $a_i$ 段的某一点。例如，下图展示了当 $n=7$ 且 $a=[4,1,4,6,7,7,5]$ 时的两种可能的连线方式。  当两根线有公共点时，称为一次“交叉”。上图中，交叉处用红圈标出。 如果你可以最优地放置这些线，最多能有多少次交叉？

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示数组的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$），表示数组的元素。 所有测试用例中 $n$ 的总和不超过 $1000$。

对于每个测试用例，输出一个整数，表示在最优放置线的情况下，最多能有多少次交叉。

第一个测试用例在题目描述的第二张图中已经展示。 第二个测试用例中，唯一的连线方式会有两根线交叉，因此答案为 $1$。 第三个测试用例中，只有一根线，因此答案为 $0$。 由 ChatGPT 4.1 翻译