Eliminate Laogou

You are given a permutation A = a₁, a₂, \(\cdots\), a_n of length \(n\). For each index \(i\) (\(1 \le i \le n\)), define

\[ S_i = \{x\mid x \ge i \ \text{and}\ \max_{i \le k \le x} a_k \le a_x\}\]

This can be interpreted as the set of indices (starting from \(i\)) at which the prefix (of the suffix starting at \(i\)) reaches a new maximum. For example, if \(A = \{3,5,2,1,4\}\), then \(S_1 = \{1,2\}\) and \(S_3 = \{3,5\}\).

You are further given \(q\) queries. Each query is described by two integers \(l\) and \(r\). For each query, you need to compute the value:

\[ \left(\left(\sum_{l \le x \le y \le r} |S_x \cup S_y| - \sum_{\substack{1 \le x < l \\ r < y \le n}} |S_x \cup S_y| \right) \bmod P + P \right) \bmod P, \]

where \(P = 998244353\). In the first summation, the sum is taken over all pairs \((x,y)\) with \(l \le x \le y \le r\). In the second summation, the sum is taken over all pairs \((x,y)\) with \(1 \le x < l\) and \(r < y \le n\).

Your task is to answer all queries.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n \le 10^3,\ 1 \le q \le 10^3)\) — the length of the permutation and the number of queries.

The second line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\) representing the permutation.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) describing a query.

outputFormat

For each query, output one line containing the corresponding answer as described in the problem statement.

sample

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

33
14
9

</p>