Description

注意：问题 "Reversort" 和 "Reversort Engineering" 的题目描述主体部分相同，仅最后一段不同。这两个问题可以独立解决。

Reversort 是一种用于将互不相同的整数列表按升序排序的算法。该算法基于 "Reverse" 操作，每次应用该操作会反转列表中某个连续部分的顺序。

算法的伪代码如下：

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

经过 $i-1$ 次迭代后，列表的第 $1, 2, \ldots, i-1$ 个位置将包含 $L$ 中前 $i-1$ 小的元素，并按升序排列。在第 $i$ 次迭代中，算法会反转从第 $i$ 个位置到当前第 $i$ 小元素所在位置的子列表。这将使第 $i$ 小的元素最终位于第 $i$ 个位置。

例如，对于一个包含 4 个元素的列表，算法将执行 3 次迭代。以下是处理 $L = [4, 2, 1, 3]$ 的过程：

1. $i = 1$，$j = 3 \longrightarrow L = [1, 2, 4, 3]$
2. $i = 2$，$j = 2 \longrightarrow L = [1, 2, 4, 3]$
3. $i = 3$，$j = 4 \longrightarrow L = [1, 2, 3, 4]$

在我们的架构中，执行该算法最耗时的部分是 Reverse 操作。因此，我们衡量每次迭代成本的标准仅仅是传递给 Reverse 的子列表长度，即 $j - i + 1$。整个算法的成本是每次迭代成本的总和。

在上述示例中，迭代成本依次为 3、1 和 2，总成本为 6。

给定初始列表，计算执行 Reversort 的成本。

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。每个测试用例包含 2 行。第一行包含一个整数 $\mathbf{N}$，表示输入列表的元素数量。第二行包含 $\mathbf{N}$ 个互不相同的整数 $\mathbf{L}_{1}, \mathbf{L}_{2}, \ldots, \mathbf{L}_{\mathbf{N}}$，按顺序表示输入列表 $L$ 的元素。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是对给定列表执行 Reversort 的总成本。

3
4
4 2 1 3
2
1 2
7
7 6 5 4 3 2 1

Case #1: 6
Case #2: 1
Case #3: 12

Hint

样例解释

样例 #1 已在题目描述中说明。

在样例 #2 中，仅有一次迭代，Reverse 操作应用于长度为 1 的子列表，因此总成本为 1。

在样例 #3 中，第一次迭代反转了整个列表，成本为 7。此后列表已排序，但仍有 5 次迭代，每次成本为 1。

数据范围

测试集 1（7 分，可见判定结果）

• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{N} \leq 100$。
• $1 \leq \mathbf{L}_{i} \leq N$，对所有 $i$ 成立。
• $\mathbf{L}_{i} \neq \mathbf{L}_{j}$，对所有 $i \neq j$ 成立。

翻译由 DeepSeek V3 完成