题目背景

二维莫队构造可以看作 $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$ 取模。

3 3
1 2 3
1 2
1 3
2 3

3

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

12

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

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$ 的排列。