题意理解

有一个长度为 $n$ 的排列 $p$，还有 $m$ 个区间 $[l_i, r_i]$。

对每个区间 $i$，我们需要选择一个位置 $k_i$，满足 $l_i \le k_i < r_i$，然后定义：

$$a_i = \max_{j = l_i}^{k_i} p_j,\quad b_i = \min_{j = k_i+1}^{r_i} p_j $$

要求：

$$\max_{i=1}^m a_i \;<\; \min_{i=1}^m b_i$$

换句话说，存在一个 $X$，使得所有 $a_i \le X$，所有 $b_i > X$。
即每个区间左半部分的最大值 $\le X$，右半部分的最小值 $> X$。

---

第一步：转化为“分割值”问题

设 $X$ 是一个值，将排列 $p$ 中所有 $\le X$ 的数称为“小”，$> X$ 的数称为“大”。
那么条件等价于：
对每个区间 $[l_i, r_i]$，都存在一个分割点 $k_i$，使得 $[l_i, k_i]$ 全为小，$[k_i+1, r_i]$ 全为大。

换句话说，每个区间内部不能出现“小-大-小”或“大-小-大”的交替模式，只能有一段连续的小（可以是空）和一段连续的大（可以是空），且小在左，大在右。

---

第二步：对位置的限制

如果我们知道 $X$ 的值，那么每个位置的颜色就确定了：
如果 $p_j \le X$ 则白色（小），否则黑色（大）。

那么每个区间必须满足：存在一个 $k_i$，使得区间 $[l_i, k_i]$ 全是白色，$[k_i+1, r_i]$ 全是黑色。

这等价于：

• 区间内不能出现白色在黑色右边的情况，因为那样的话，无论怎么选 $k_i$，都无法让左边全是白、右边全是黑。
• 但更精确地说：区间内不能同时存在白-黑-白或黑-白-黑，只能单调。

实际上，这个条件可以转化为：在区间 $[l_i, r_i]$ 中，如果某个位置是白色，则它之前的所有位置（在这个区间内）也必须是白色；如果某个位置是黑色，则它之后的所有位置（在这个区间内）也必须是黑色。
即颜色在区间内是单调的（先白后黑）。

---

第三步：区间合并与块划分

如果两个区间有重叠，那么它们会对颜色顺序产生更强的约束。

假设我们有区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，且它们重叠。
在 $[l_1, r_1]$ 内部颜色是单调的，在 $[l_2, r_2]$ 内部颜色也是单调的。
如果两个区间重叠，那么重叠部分的颜色必须同时满足两个区间的单调性，这就强制了在 $[l_1, r_2]$ 或 $[l_2, r_1]$ 等更大范围内颜色也是单调的。

最终，所有区间会把整个排列分成若干个“块”，每个块内部必须同色（全是白或全是黑），并且块与块之间的颜色是交替的？不一定，因为可以连续多个白块再连续多个黑块。

更准确地说：考虑所有区间的并集，如果某些位置被强制要么同时白要么同时黑，那就合并成一个“等价类”。
等价类之间有一个偏序关系：如果某个等价类在另一个等价类的左边，且它们之间有约束，那它们可以不同色。

---

第四步：转化为图论模型

一种经典转化：

对每个位置 $i$，定义变量 $x_i \in \{0,1\}$，$0$ 表示白色（小），$1$ 表示黑色（大）。

每个区间 $[l_i, r_i]$ 要求：存在一个 $k_i$，使得 $x_{l_i} = \dots = x_{k_i} = 0$，且 $x_{k_i+1} = \dots = x_{r_i} = 1$。

换句话说，区间内的 $x$ 序列是单调不降的（从 0 到 1，可以全 0 或全 1）。

单调不降意味着：对区间内任意 $u < v$，不能有 $x_u = 1$ 且 $x_v = 0$。
即不存在“先 1 后 0”的模式。

这等价于：对每个区间 $[l_i, r_i]$，如果存在 $u, v$ 满足 $l_i \le u < v \le r_i$ 且 $x_u = 1, x_v = 0$，则违反条件。
也就是区间内不能出现“1 在 0 左边”。

---

第五步：不等式约束

这个“1 不能在 0 左边”等价于：对区间内任意 $u < v$，$x_u \le x_v$。
但这是对所有 $u, v$ 吗？不，是对区间内所有相邻的位置吗？其实只需要相邻的，因为传递性。

更简洁：区间内必须满足 $x$ 是非降的，即 $x_{l_i} \le x_{l_i+1} \le \dots \le x_{r_i}$。

所以每个区间给出了一串不等式：$x_j \le x_{j+1}$ 对所有 $j \in [l_i, r_i-1]$。

---

第六步：不等式系统与等价类

对所有区间收集这样的相邻不等式，就得到一个偏序关系：某些位置必须 $\le$ 后面的位置。

如果有 $x_u \le x_v$ 且 $x_v \le x_u$，则 $x_u = x_v$，即它们必须同色。
这可以用并查集合并：对所有 $u, v$，如果 $x_u \le x_v$ 且 $x_v \le x_u$，则 $u$ 和 $v$ 在同一等价类。

那么剩下的约束是等价类之间的顺序：如果 $u$ 的等价类在 $v$ 的等价类左边，且 $u$ 必须 $\le v$，那么 $x_u = 0$ 时 $x_v$ 可以是 0 或 1，但 $x_u=1$ 时 $x_v$ 必须是 1。

---

第七步：最大化逆序对

给定等价类之间的 DAG，我们要给每个等价类赋 0 或 1，使得所有有向边 $u \to v$ 满足 $x_u \le x_v$，并且最大化逆序对数。

逆序对定义：$i<j$ 且 $p_i > p_j$。
如果 $x_i=1$（大）且 $x_j=0$（小），那么不管具体数值如何，$p_i > p_j$ 必然成立（因为我们把 $\le X$ 的放一起，$>X$ 的放一起，且大类所有数大于小类所有数）。
如果 $x_i=x_j$，则逆序对取决于内部排列。

但为了最大化逆序对，我们会在每个等价类内部，让数按降序排列（这样内部逆序对最多），并且让 $=1$ 的等价类（大类）全部排在 $=0$ 的等价类（小类）左边，这样大类和小类之间产生全部可能的逆序对。

---

第八步：构造最优排列

1. 确定 $X$ 的值：实际上 $X$ 是等价类划分的一个阈值。最终所有 $x=0$ 的等价类里的数都 $\le X$，所有 $x=1$ 的等价类里的数 $>X$。
2. 我们把 $x=1$ 的等价类里的数（按降序排列）放在最左边，$x=0$ 的等价类里的数（按降序排列）放在最右边，这样大类全部大于小类，并且内部逆序对最大。
3. 这样总逆序对数 = 大类内部逆序对数 + 小类内部逆序对数 + 大类与小类之间的逆序对数。
   • 大类与小类之间的逆序对数 = 大类元素个数 × 小类元素个数。
   • 内部逆序对数 = $\sum_{每个等价类} \binom{\text{size}}{2}$。

---

第九步：可行性判断

如果图中有环（通过不等式传递得到 $x_u \le x_v$ 和 $x_v \le x_u$ 但不在同一等价类），则无解。
实际上，强连通分量就是等价类。

另外，如果某个等价类必须同时 $\le$ 和 $>$ 另一个等价类，也会无解。

更简单的判断：对所有 $i$ 检查是否所有区间都能满足单调性。如果某个区间内已经存在等价类顺序矛盾（比如 $a$ 必须在 $b$ 左边，但 $b$ 必须在 $a$ 左边），则无解。

---

第十步：算法步骤总结

1. 读入 $n, m$ 和所有区间。
2. 对每个区间 $[l_i, r_i]$，添加约束 $x_{j} \le x_{j+1}$ 对所有 $j \in [l_i, r_i-1]$。
3. 用并查集合并所有 $x_u \le x_v$ 且 $x_v \le x_u$ 的点对（通过传递闭包或直接找环）。
4. 如果发现矛盾（比如 $a<b$ 且 $b<a$ 且不在同一等价类），输出 -1。
5. 否则，等价类之间形成 DAG。我们选择一个拓扑序，把所有 $x=1$ 的等价类放在左边，$x=0$ 的放在右边（这个选择是唯一的，因为所有有向边必须 $0\to 1$ 或 $0\to 0$ 或 $1\to 1$，不能 $1\to 0$）。
6. 计算逆序对：
   • 设 $cnt1$ = 所有 $x=1$ 的等价类的大小之和，$cnt0$ = 所有 $x=0$ 的等价类的大小之和。
   • 总逆序对 = $cnt1 \times cnt0$ + $\sum \binom{\text{size}_c}{2}$ 对所有等价类 $c$。
7. 输出这个最大逆序对数。

---

最终公式

设 $S_1$ 为 $x=1$ 的等价类的大小集合，$S_0$ 为 $x=0$ 的等价类的大小集合，则：

$$\text{ans} = \left( \sum_{a \in S_1} a \right) \cdot \left( \sum_{b \in S_0} b \right) + \sum_{c \in S_1 \cup S_0} \binom{\text{size}_c}{2} $$

并且 $S_1$ 和 $S_0$ 的划分由 DAG 的拓扑序唯一确定（所有可以放 1 的放左边，其余 0）。