Background

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

Compute the minimum spanning tree, then take all vertices with odd degree, and run a minimum-weight matching on the induced subgraph to obtain $E$. Add $E$ to the minimum spanning tree, and then find an Euler tour.

Note that $\text{MST}(S)\le \text{TSP}(S)$, $2E\le \text{TSP}(S)$ (a $\text{TSP}$ solution for $E$ can give two matchings; consider the smaller one), and the total edge weight of the Euler tour is no less than the weight of the solution given by the Euler tour, which yields 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-domain interval $[L, R]$:

• Define the “value of this value-domain interval when choosing $i$” as how many numbers in $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ belong to the value-domain interval $[L, R]$.
• Define the value of the value-domain interval $[L, R]$ as the maximum of the above quantity over all $\forall i \in [1, m]$.

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

Two intervals are defined to intersect if and only if there exists at least one integer contained in both intervals. Please choose several pairwise non-intersecting value-domain intervals such that the product of their values is maximized. Output this answer modulo $998244353$.

Input Format

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

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

The next $m$ lines each contain two integers $l_i, r_i$.

Output Format

Output one integer denoting the answer. Output the answer modulo $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

Sample Explanation 1

Choose the value-domain interval $[1,3]$.

Sample Explanation 2

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

Sample Explanation 3

Sample 3 satisfies the special property.

Constraints and Notes

This problem uses bundled testdata.

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

For all testdata, 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$.

Translated by ChatGPT 5