题目描述

定义一个序列的权值为：

• 若序列长度为 $1$，则其权值为 $0$。

• 否则，其权值为最小值乘次小值乘最大值，此处次小值是非严格的。

给定一个序列 $a$，$q$ 次询问 $l,r$，问 $a_l,a_{l+1},\dots,a_r$ 组成的序列的所有子序列的权值和。对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,q$，表示序列长度和询问次数。

第二行 $n$ 个正整数 $a_i$，表示该序列。

接下来 $q$ 行每行两个正整数 $l,r$，表示询问区间。

输出格式

$q$ 行每行一个整数，表示答案。

样例一

input

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

output

4
0
37
81

样例二

见下发文件中的 $\text{ex_mulsign2.in/ans}$，此样例满足子任务 $1$ 的限制。

样例三

见下发文件中的 $\text{ex_mulsign3.in/ans}$，此样例满足子任务 $4$ 的限制。

样例四

见下发文件中的 $\text{ex_mulsign4.in/ans}$，此样例满足子任务 $6$ 的限制。

限制与约定

对于所有数据，满足 $1\le n\le 2.5\times 10^4,1\le q\le 1\times 10^5,1\le a_i\le 10^9,1\le l\le r\le n$。