CF1827B1 Range Sorting (Easy Version)

本题与难度更高的版本唯一的区别在于 $ t $ 和 $ n $ 的约束条件。 给定一个由 $ n $ 个互不相同的整数 $ a_1, a_2, \ldots, a_n $ 组成的数组 $ a $。 定义一个数组 $ p_1, p_2, \ldots, p_k $ 的“美丽值”为使用任意次数的区间排序操作将该数组排序所需的最少时间。每次区间排序操作，你可以： - 选择两个整数 $ l $ 和 $ r $（$ 1 \le l < r \le k $）。 - 将子数组 $ p_l, p_{l + 1}, \ldots, p_r $ 排序，耗时为 $ r - l $ 秒。 请计算数组 $ a $ 的所有子数组的美丽值之和。 一个数组的子数组定义为该数组中一段连续的元素序列。

每组测试数据包含多个测试用例。第一行包含测试用例数 $ t $（$ 1 \le t \le 5 \cdot 10^3 $）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 5 \cdot 10^3 $），表示数组 $ a $ 的长度。 第二行包含 $ n $ 个整数 $ a_1,a_2,\ldots, a_n $（$ 1\le a_i\le 10^9 $）。保证所有元素两两不同。 保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^3 $。

对于每个测试用例，输出数组 $ a $ 所有子数组的美丽值之和。

在第一个测试用例中： - 子数组 $ [6] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [4] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [6, 4] $ 可以通过一次操作排序，选择 $ l = 1 $，$ r = 2 $，美丽值为 $ 1 $。 因此，给定数组所有子数组的美丽值之和为 $ 0 + 0 + 1 = 1 $。 在第二个测试用例中： - 子数组 $ [3] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [10] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [6] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [3, 10] $ 已经有序，所以美丽值为 $ 0 $。 - 子数组 $ [10, 6] $ 可以通过一次操作排序，选择 $ l = 1 $，$ r = 2 $，美丽值为 $ 2 - 1 = 1 $。 - 子数组 $ [3, 10, 6] $ 可以通过一次操作排序，选择 $ l = 2 $，$ r = 3 $，美丽值为 $ 3 - 2 = 1 $。 因此，给定数组所有子数组的美丽值之和为 $ 0 + 0 + 0 + 0 + 1 + 1 = 2 $。 由 ChatGPT 4.1 翻译