P9152 To Be Clearly Black and White.

.

The city where [Shiro](https://www.bilibili.com/video/BV1jb411k7wa) lives can be viewed as $n$ consecutive points on a number line. The height of point $i$ is $p_i$, and it is guaranteed that $p$ is a permutation of $\{1,2,\ldots,n\}$. In the year 3202, technology is highly advanced, and wormhole train technology has been developed. There are $n$ types of trains. The $i$-th type of train passes through all positions whose height is at least $i$. Each train line is bidirectional, meaning you can take the train from left to right or from right to left. Shiro wants to travel around the city. She defines a set of positions $S$ to be valid if and only if, after sorting the positions in $S$ **by height**, each pair of adjacent positions in this order can be traveled between directly by taking **one** type of train without stopping in between. She will ask you $q$ queries. In each query, you are given $l,r$, and you need to tell Shiro the number of valid sets $T$ such that the **heights** of all positions are within $[l,r]$, modulo $998244353$.

The first line contains two positive integers $n,q$. The second line contains $n$ positive integers, representing $p_{1,2,\ldots,n}$. The next $q$ lines each contain two positive integers $l_i, r_i$, representing the height interval of the $i$-th query.

Output $q$ lines. Each line contains one non-negative integer, representing the answer.

**Sample Explanation** Explanation for the first query: The valid height sets are: $\{3\},\{4\},\{5\},\{3,5\},\{4,5\}$. --- **Constraints** For $100\%$ of the testdata, $1\le n,q\le 2\times {10}^5$, $p$ is a permutation, and $1\le l_i \le r_i \le n$. |Subtask|$n\le$|$q\le$|Special Property|Score| |-|-|-|-|-| |1|$15$|$1000$||$10$| |2|$1000$|$1000$||$15$| |3|||A|$5$| |4|||B|$30$| |5|$5\times{10}^4$|$5\times{10}^4$||$20$| |6||||$20$| Special Property A: $p_i=i$. Special Property B: $p$ is chosen uniformly at random from all permutations of length $n$. Translated by ChatGPT 5