[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
3 3
1 2 3
1 2
1 3
2 3输出样例 #1
3输入样例 #2
10 10
7 9 4 5 8 3 2 1 6 10
3 7
2 6
1 2
3 4
8 9
1 2
2 6
5 8
6 9
4 5输出样例 #2
12输入样例 #3
60 30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
34 57
2 17
3 16
18 50
18 54
8 45
8 56
14 39
22 33
12 33
27 49
33 33
9 11
12 52
11 17
23 31
14 39
19 57
25 32
15 22
2 48
14 21
51 59
28 48
26 31
31 60
41 58
36 46
49 53
44 48输出样例 #3
328034228说明
### 样例解释 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$ 的排列。