Legal City Subset

In a futuristic city in the year 3202, there are (n) cities arranged in a line (number axis). Each city has a unique height, given by the permutation (p = [p_1, p_2, \dots, p_n]) of ({1,2,\dots,n}) (i.e. the (i)th city has height (p_i)). There are also (n) types of wormhole trains. The (i)th train stops exactly at those cities whose height is at least (i) (i.e. at all cities satisfying (p_j \ge i)). All train lines are bidirectional so one can travel in either direction without changing trains.

Shiro defines a set (S) (a set of city positions) to be legal if and only if, after sorting the cities in (S) in increasing order of their height, every pair of consecutive cities can be connected directly by riding a single train (without any intermediate stops). Formally, let (S = {a_1, a_2, \dots, a_k}) be a nonempty set of positions such that (p_{a_1} < p_{a_2} < \cdots < p_{a_k}). For every adjacent pair (a_i) and (a_{i+1}) ((1 \le i < k)), there must exist a train type (r) (you may take (r = p_{a_i})) such that the train stops at both positions and the two stops are consecutive. That is, if we let (L = \min(a_i,a_{i+1})) and (R = \max(a_i,a_{i+1})), then for every city position (j) with (L < j < R), it must hold that (p_j < p_{a_i}).

You are given (q) queries. In each query, you are given two integers (l) and (r). Consider the set of cities whose heights lie in the interval ([l,r]). Let (T) be any legal (nonempty) subset of these cities (when considered in the original city positions). Your task is to compute the number of legal subsets (T) modulo (998244353).

inputFormat

The first line contains two integers (n) and (q) (the number of cities and the number of queries).
The second line contains (n) space-separated integers (p_1, p_2, \dots, p_n), which form a permutation of ({1, 2, \dots, n}).
Each of the next (q) lines contains two integers (l) and (r) representing a query.

outputFormat

For each query, output a single line containing the number of legal subsets (T) (consisting of one or more cities with heights in ([l,r])) modulo (998244353).

sample

3 2
1 2 3
1 2
2 3

3
3