[Shiro](https://www.bilibili.com/video/BV1jb411k7wa) 所在的城市可以看成数轴上 $n$ 个坐标连续的点，其中 $i$ 号点的高度为 $p_i$，保证 $p$ 是一个 $\{1,2,\ldots,n\}$ 的排列。
3202 年的科技非常发达，发展出了虫洞列车技术。共有 $n$ 种列车，第 $i$ 种列车会经过所有高度大于等于 $i$ 的位置，每种列车线路都是双向的，也就是说可以乘列车从左到右，也可以从右到左。
Shiro 想在城市里转转，她定义一个位置集合 $S$ 合法，当且仅当我们将 $S$ 中的位置**按照高度排序**后，相邻的城市可以通过乘坐**一种**列车在中途不停靠的情况下直达。
她会给你 $q$ 次询问，每次给定 $l,r$，你需要告诉 Shiro 所有位置的**高度**均在 $[l,r]$ 内的合法集合 $T$ 的数量对 $998244353$ 取模的结果。
## Input
第一行，两个正整数 $n,q$。
第二行，$n$ 个正整数，表示 $p_{1,2,\ldots,n}$。
接下来 $q$ 行，第 $i$ 行两个正整数 $l_i, r_i$，表示第 $i$ 次询问的高度区间。
## Output
输出 $q$ 行，每行一个非负整数，表示答案。
[samples]
## Note
**【样例解释】**
第一组询问解释：
合法的高度集合有：$\{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$。
|子任务|$n\le$|$q\le$|特殊性质|分值|
|-|-|-|-|-|
|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$|
特殊性质 A：$p_i=i$。
特殊性质 B：$p$ 在所有长度为 $n$ 的排列中随机选取。