Background

.

Problem Description

The city where Shiro 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$.

Input Format

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 Format

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

5 3
2 4 5 1 3
3 5
1 5
1 4

5
12
6

Hint

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$.

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