Description

给你一个 $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$ 取模后输出。

Input Format

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示 $a_{1\dots n}$。

下面 $m$ 行，每行两个整数 $l_i,r_i$。

Output Format

一个整数表示答案。输出答案时对 $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

Hint

样例解释 1

选择值域区间 $[1,3]$。

样例解释 2

可以选择值域区间 $[1,3],[4,5],[8,10]$。

样例解释 3

样例 3 满足特殊性质。

数据规模与约定

本题采用捆绑测试。

特殊性质：保证 $\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$ 的排列。