CF1566D1 Seating Arrangements (easy version)

这是该问题的简单版本。唯一的区别是本版本中 $n = 1$。 在电影院中，座位可以表示为一个有 $n$ 行 $m$ 列的表格。行号从 $1$ 到 $n$。每一行的座位从左到右依次编号：第 $k$ 行的座位编号为 $m(k-1)+1$ 到 $mk$，对于所有 $1 \leq k \leq n$ 的行。 $$ \begin{aligned} &1 \\ &2 \quad \cdots \quad m-1 \quad m \quad m+1 \\ &m+2 \quad \cdots \quad 2m-1 \quad 2m \quad 2m+1 \\ &2m+2 \quad \cdots \quad 3m-1 \quad 3m \quad \vdots \\ &\vdots \quad \ddots \quad \vdots \quad \vdots \quad m(n-1)+1 \\ &m(n-1)+2 \quad \cdots \quad nm-1 \quad nm \end{aligned} $$ 上表为座位编号表。 有 $nm$ 个人想去电影院观看新电影。他们编号为 $1$ 到 $nm$。你需要为每个人分配一个且仅一个座位。 已知在这个电影院中，座位编号越小，观影效果越好。第 $i$ 个人的视力等级为 $a_i$。设 $s_i$ 为分配给第 $i$ 个人的座位编号。你希望视力等级较低的人能获得更好的座位，因此对于任意两个人 $i$ 和 $j$，如果 $a_i < a_j$，则应满足 $s_i < s_j$。 当所有人分配好座位后，他们会依次入场并就座。按照 $1$ 到 $nm$ 的顺序，每个人进入影厅并坐到自己的座位。为了到达自己的座位，这个人会走到所在行，并从该行的第一个座位向右依次走到自己的座位。在行进过程中，有些座位是空的，有些已经被其他人占据。这个人的“不便度”定义为他经过的已被占据的座位数。 举个例子：$m=5$，某人被分配到第一行的第 $4$ 号座位，第一行的 $1$、$3$、$5$ 号座位已经被占据，$2$ 和 $4$ 号座位是空的。这个人的不便度为 $2$，因为他经过了已被占据的 $1$ 和 $3$ 号座位。 请你计算，在满足所有条件的情况下，分配座位使得总不便度最小是多少。

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$n=1$，$1 \leq m \leq 300$），分别表示行数和每行的座位数。 每个测试用例的第二行包含 $n \cdot m$ 个整数 $a_1, a_2, \ldots, a_{n \cdot m}$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 个人的视力等级。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示可以获得的最小总不便度。

在第一个测试用例中，只有一种分配方式，因为所有视力等级都不同。第一个人坐在第一个座位，第二个人坐在第二个座位，第三个人坐在第三个座位。因此，第一个人的不便度为 $0$，第二个人为 $1$，第三个人为 $2$。总不便度为 $0+1+2=3$。 在第二个测试用例中，分配应为：$s_1=2$，$s_2=1$，$s_3=5$，$s_4=4$，$s_5=3$。总不便度为 $6$。 由 ChatGPT 4.1 翻译