Problem Background

The construction of 2D Mo's algorithm can be seen as a TSP problem on a complete graph where the edge weights between $i$ and $j$ are $|l_i - l_j| + |r_i - r_j|$. Clearly, any edge weight in Mo's algorithm satisfies the triangle inequality.

Find the minimum spanning tree, then take all vertices with odd degrees and run the minimum weight matching on this induced subgraph to get $E$. Add $E$ to the minimum spanning tree and then run the Eulerian path.

Notice that $\text{MST}(S) \le \text{TSP}(S)$, $2E \le \text{TSP}(S)$ (the TSP solution of $E$ can give two sets of matches, consider the smaller one) and the edge weight sum of the Eulerian path is not less than the weight of the solution given by the Eulerian path, which gives a result $\le 1.5 \text{TSP}(S)$.

Problem Description

You are given a permutation $a$ of $1 \sim n$ and $m$ intervals $[l_i, r_i]$ on this permutation.

For a value range interval $[L, R]$:
- The "value of the value range interval when selecting $i$" is the number of elements in $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ that belong to the value range interval $[L, R]$;
- Define the value of the value range interval $[L, R]$ as the maximum of "the value of the value range interval when selecting $i$" for all $i \in [1, m]$.

That is, the value of the value range interval $[L, R]$ is $\displaystyle\max_{i=1}^m \sum_{j=l_i}^{r_i} [L \le a_j \le R]$.

Define two intervals as intersecting if and only if there is at least one integer contained in both intervals. Please select several disjoint value range intervals such that the product of their values is maximized. Output the answer modulo $998244353$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers representing $a_{1 \dots n}$.

The following $m$ lines, each containing two integers $l_i, r_i$.

Output Format

An integer representing the answer. Output the answer modulo $998244353$.

Sample Input and Output

Input Sample #1

3 3
1 2 3
1 2
1 3
2 3

Output Sample #1

3

Input Sample #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

Output Sample #2

12

Input Sample #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

Output Sample #3

328034228

Notes

Sample Explanation 1

Choose the value range interval $[1, 3]$.

Sample Explanation 2

You can choose the value range intervals $[1, 3], [4, 5], [8, 10]$.

Sample Explanation 3

Sample 3 satisfies the special property.

Data Size and Constraints

This problem uses batched testing.

Special Property: It is guaranteed that $\forall i \in [1, n], a_i = i$.

For all data, it is guaranteed that $1 \le n, m \le 3 \times 10^5$, $1 \le l_i \le r_i \le n$, and $a$ is a permutation of $1 \sim n$.

见题面 Input 部分

见题面 Output 部分