P10880 [JRKSJ R9] 莫队的 1.5 近似构造

二维莫队构造可以看作 $i,j$ 之间有权值为 $|l_i-l_j|+|r_i-r_j|$ 的完全图上的 TSP 问题。显然，任何莫队的边权都满足三角不等式。 求出最小生成树，然后把所有度数为奇数的点拿出来，对这个导出子图跑最小权匹配得到 $E$，将 $E$ 加到最小生成树上，然后跑欧拉路径即可。 注意到 $\text{MST}(S)\le \text{TSP}(S)$，$2E\le \text{TSP}(S)$（$E$ 的 $\text{TSP}$ 方案可以给出两组匹配，考虑其中的较小值）且欧拉路径的边权和不小于欧拉路径给出的方案的权值，就给出了 $\le 1.5\text{TSP}(S)$ 的结果。

给你一个 $1\sim n$ 的排列 $a$ 和 $m$ 个该排列上的区间 $[l_i,r_i]$。 对于一个值域区间 $[L,R]$： - 称「选取 $i$ 时该值域区间的价值」为 $a_{l_i},a_{l_i+1},\dots,a_{r_i}$ 中有多少个数属于值域区间 $[L,R]$； - 定义值域区间 $[L,R]$ 的价值为 $\forall i\in[1,m]$，「选取 $i$ 时该值域区间的价值」的最大值。 即，值域区间 $[L,R]$ 的价值为 $\displaystyle\max_{i=1}^m \sum_{j=l_i}^{r_i} [L\le a_j\le R]$。 定义两个区间相交当且仅当至少有一个整数被这两个区间共同包含。请你选出若干个**互不相交**的值域区间，使得它们的价值的乘积最大。将该答案对 $998244353$ 取模后输出。

第一行两个整数 $n,m$。 第二行 $n$ 个整数表示 $a_{1\dots n}$。 下面 $m$ 行，每行两个整数 $l_i,r_i$。

一个整数表示答案。输出答案时对 $998244353$ 取模。

### 样例解释 1 选择值域区间 $[1,3]$。 ### 样例解释 2 可以选择值域区间 $[1,3],[4,5],[8,10]$。 ### 样例解释 3 样例 3 满足特殊性质。 ### 数据规模与约定 **本题采用捆绑测试。** | $\mathrm{Subtask}$ | $n,m\le$ | 特殊性质 | 分数 | | :-----: | :-----: | :-----: | :-----: | | $1$ | $20$ | | $10$ | | $2$ | $5\times 10^3$ | | $15$ | | $3$ | $3\times 10^5$ | $\checkmark$ | $10$ | | $4$ | $5\times 10^4$ | | $25$ | | $5$ | $3\times 10^5$ | | $40$ | 特殊性质：保证 $\forall i\in[1,n],a_i=i$。 对于所有数据，保证 $1\le n,m\le 3\times 10^5$，$1\le l_i\le r_i\le n$，$a$ 是一个 $1\sim n$ 的排列。