这是这个问题的简单版本。版本之间的差异在于 $$$m$$$ 和 $$$r_i < l_{i + 1}$$$ 的约束对于简单版本中从 $$$1$$$ 到 $$$m - 1$$$ 的每个 $$$i$$$ 成立。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Turtle 为您提供 $$$m$$$ 间隔 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$。他认为如果每个区间都存在一个整数 $$$k_i$$$ ($$$l_i \le k_i < r_i$$$),并且让 $$$a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i},那么排列 $$$p$$$ 是有趣的p_j$$$ 对于从 $$$1$$$ 到 $$$m$$$ 的每个整数 $$$i$$$,以下条件成立:
$$$$$$\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i$$$$$$
Turtle 要你计算长度为 $$$n$$$ 的所有有趣排列的最大反转次数,或者告诉他是否没有有趣的排列。
排列 $$$p$$$ 的逆是一对整数 $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) 使得 $$$p_i > p_j$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$2 \le n \le 5 \cdot 10^3, 0 \le m \le \frac{n}{2}$$$) — 排列的长度和间隔的数量。
以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 第 $$$i$$$ 个区间。
此版本中输入的附加约束:$$$r_i < l_{i + 1}$$$ 对于从 $$$1$$$ 到 $$$m - 1$$$ 的每个 $$$i$$$ 成立。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^3$$$。
输出
对于每个测试用例,如果没有有趣的排列,则输出单个整数 $$$-1$$$。
否则,输出一个整数——最大反转次数。
示例
输入 #1
6 2 0 2 1 1 2 5 1 2 4 8 2 1 4 6 8 7 2 1 3 4 7 7 3 1 2 3 4 5 6
输出 #1
1 0 8 21 15 15
注意
在第三个测试用例中,具有最大反转次数的有趣排列是 $$$[5, 2, 4, 3, 1]$$$。
在第四个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 8, 7, 6, 3, 2, 1, 5]$$$。在这种情况下,我们可以让 $$$[k_1, k_2] = [1, 7]$$$。
在第五个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 7, 6, 3, 2, 1, 5]$$$。
在第六个测试用例中,具有最大反转次数的有趣排列是 $$$[4, 7, 3, 6, 2, 5, 1]$$$。