U470659 再见宣言

《再见宣言》是疫情期间的歌，但即使现在是 2024，并不是疫情期间，Square 仍然喜欢在家里宅着听《再见宣言》。

Square 有 $n$ 个时间段听歌，每个时间段 Square 会听一首悦耳度为 $v_i$ 的歌。 定义一个听歌的时间段 $[l,r]$ 的“正义程度”为 $\sum_{i=l}^r[v_i \ge \max(v_l,v_r)] \times \sum_{i=l}^r[v_i \ge \max(v_l,v_r)]v_i$。 然而，Square 并不是那么正义，所以 Square 会对计算的结果取模 $998244353$。 现在 Square 想知道，对于给出的 $[l,r]$，这一段时间的“正义程度”是多少？

第一行，给出两个整数 $n$ 和 $m$，表示 Square 听歌的时间段的长度和询问的个数。 第二行，给出 $n$ 个整数 $v_1,v_2,\ldots,v_n$，$v_i$ 表示第 $i$ 个时间段听的歌的悦耳度。 接下来 $m$ 行，每行两个整数 $l,r$，表示 Square 的一次询问。

对于每次询问，输出一行一个整数，代表这一段区间的“正义程度”。

对于 $30\%$ 的数据，$n,m \le 5000$。 对于 $100\%$ 的数据，$1 \le n,m \le 10^5,0 \le v_i \le 10^7$。 **家里蹲才是绝对正义！！！**