这个问题和困难版本之间的唯一区别是对 $$$t$$$ 和 $$$n$$$ 的约束。
给定一个数组 $$$a$$$,由 $$$n$$$ 个不同的整数 $$$a_1、a_2、\ldots、a_n$$$ 组成。
将数组 $$$p_1, p_2, \ldots p_k$$$ 的美妙之处定义为使用任意数量的范围排序操作对该数组进行排序所需的最短时间。在每个范围排序操作中,您将执行以下操作:
- 选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le k$$$)。
- 在 $$$r - l$$$ 秒内对子数组 $$$p_l, p_{l + 1}, \ldots, p_r$$$ 进行排序。
请计算数组 $$$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$$$) 组成。保证 $$$a$$$ 的所有元素都是成对不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^3$$$。
输出
对于每个测试用例,输出数组 $$$a$$$ 的所有子数组的美感总和。
示例
输入 #1
5 2 6 4 3 3 10 6 4 4 8 7 2 5 9 8 2 4 6 12 2 6 13 3 15 5 10 8 16 9 11 18
输出 #1
1 2 8 16 232
注意
在第一个测试用例中:
- 子数组 $$$[6]$$$ 已经排序,所以它的优点是 $$$0$$$。
- 子数组 $$$[4]$$$ 已经排序,所以它的美丽在于 $$$0$$$。
- 您可以通过选择 $$$l = 1$$$ 和 $$$r = 2$$$ 在一次操作中对子数组 $$$[6, 4]$$$ 进行排序。它的美丽等于$$$1$$$。
在第二个测试用例中:
- 子数组 $$$[3]$$$ 已经排序,因此它的优点是 $$$0$$$。
- 子数组 $$$[10]$$$ 已经排序,所以它的优点是 $$$0$$$。
- 子数组 $$$[6]$$$ 已经排序,所以它的优点是 $$$0$$$。
- 子数组 $$$[3, 10]$$$ 已经排序,所以它的优点是 $$$0$$$。
- 您可以通过选择 $$$l = 1$$$ 和 $$$r = 2$$$ 在一次操作中对子数组 $$$[10, 6]$$$ 进行排序。它的美度等于$$$2 - 1 = 1$$$。
- 您可以通过选择 $$$l = 2$$$ 和 $$$r = 3$$$ 在一次操作中对子数组 $$$[3, 10, 6]$$$ 进行排序。它的美度等于$$$3 - 2 = 1$$$。