题目描述

Shiro 所在的城市可以看成数轴上 $n$ 个坐标连续的点，其中 $i$ 号点的高度为 $p_i$，保证 $p$ 是一个 $\{1,2,\ldots,n\}$ 的排列。

3202 年的科技非常发达，发展出了虫洞列车技术。共有 $n$ 种列车，第 $i$ 种列车会经过所有高度大于等于 $i$ 的位置，每种列车线路都是双向的，也就是说可以乘列车从左到右，也可以从右到左。

Shiro 想在城市里转转，她定义一个位置集合 $S$ 合法，当且仅当我们将 $S$ 中的位置按照高度排序后，相邻的城市可以通过乘坐一种列车在中途不停靠的情况下直达。

她会给你 $q$ 次询问，每次给定 $l,r$，你需要告诉 Shiro 所有位置的高度均在 $[l,r]$ 内的合法集合 $T$ 的数量对 $998244353$ 取模的结果。

输入格式

第一行，两个正整数 $n,q$。

第二行，$n$ 个正整数，表示 $p_{1,2,\ldots,n}$。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i, r_i$，表示第 $i$ 次询问的高度区间。

输出格式

输出 $q$ 行，每行一个非负整数，表示答案。

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

5
12
6

提示

【样例解释】

第一组询问解释：

合法的高度集合有：$\{3\},\{4\},\{5\},\{3,5\},\{4,5\}$。

【数据范围】

对于 $100 \%$ 的数据，$1\le n,q\le 2\times {10}^5$，保证 $p$ 是一个排列，且 $1\le l_i \le r_i \le n$。

特殊性质 A：$p_i=i$。

特殊性质 B：$p$ 在所有长度为 $n$ 的排列中随机选取。