Maximum Product of Value Range Intervals

Given a permutation (a) of (1) to (n) and (m) intervals ([l_i, r_i]) on the permutation, define the following for any value range interval ([L,R]) (with (1 \le L \le R \le n)):

For each given interval (i) ((1 \le i \le m)), define its value for ([L,R]) as [ c_i(L,R)=\sum_{j=l_i}^{r_i} \mathbf{1}{{L \le a_j \le R}}, ] and then the value of the value range interval ([L,R]) is defined as [ f(L,R)= \max{1\le i\le m} c_i(L,R). ]

Two value range intervals ([L_1,R_1]) and ([L_2,R_2]) are said to be non‐intersecting if they do not share any integer, i.e. ({L_1, L_1+1,\dots,R_1} \cap {L_2, L_2+1,\dots,R_2} = \emptyset).

The task is to select a collection of mutually non–intersecting value range intervals such that the product of their values is maximized. More formally, let (\mathcal{S}) be a set of pairwise disjoint intervals ([L,R]) (each a subset of ([1,n])). We want to maximize [ \prod_{[L,R]\in \mathcal{S}} f(L,R) ] and output this maximum product modulo (998244353).

It is guaranteed that an answer always exists. (Note): You must choose at least one value range interval.

inputFormat

The input is given as follows:

• The first line contains two integers (n) and (m) ((1 \le n, m \le 200)), representing the size of the permutation and the number of intervals on the permutation.
• The second line contains (n) distinct integers (a_1, a_2, \dots, a_n), which form a permutation of (1, 2, \dots, n).
• The following (m) lines each contain two integers (l_i) and (r_i) ((1 \le l_i \le r_i \le n)), defining an interval on the permutation.

outputFormat

Output a single integer, the maximum product of the values of a set of chosen non–intersecting value range intervals, taken modulo (998244353).

sample

3 1
1 2 3
1 3

3