AT_arc218_e.Reverse and Reverse

For a permutation $p=(p_1,p_2,\dots,p_N)$ of $(1,2,\dots,N)$ and a positive integer $M$, let $f(p,M)$ denote the answer to the following problem.

Perform the following operation $M$ times on $p$.

• Choose an integer $i$ with $1 \le i \le N-1$, and reverse each of $(p_1,p_2,\dots,p_i)$ and $(p_{i+1},p_{i+2},\dots,p_N)$. Formally, replace $p$ with $(p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1})$.

There are $(N-1)^M$ possible sequences of operations. Find the sum, modulo $998244353$, of "the number of inversions of $p$ after $M$ operations" over all such sequences.

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$. Process the following query $Q$ times.

• You are given an integer $x$ with $1 \le x \le N-1$ and a positive integer $K$. Swap $P_x$ and $P_{x+1}$. Then, find $f(P,K)$.

对于 $(1,2,\dots,N)$ 的一个排列 $p=(p_1,p_2,\dots,p_N)$ 和一个正整数 $M$，记 $f(p,M)$ 为如下问题的答案：

对 $p$ 执行以下操作 $M$ 次：

• 选择一个满足 $1 \le i \le N-1$ 的整数 $i$，并将 $(p_1,p_2,\dots,p_i)$ 和 $(p_{i+1},p_{i+2},\dots,p_N)$ 分别翻转。形式上，将 $p$ 替换为 $(p_i,p_{i-1},\dots,p_1,p_N,p_{N-1},\dots,p_{i+1})$。

共有 $(N-1)^M$ 种可能的操作序列。对所有这些操作序列，求“执行 $M$ 次操作后 $p$ 的逆序对数量”的总和，并对 $998244353$ 取模。

给定 $(1,2,\dots,N)$ 的一个排列 $P=(P_1,P_2,\dots,P_N)$。接下来处理 $Q$ 次查询。

• 每次查询给出一个满足 $1 \le x \le N-1$ 的整数 $x$ 和一个正整数 $K$。交换 $P_x$ 与 $P_{x+1}$，然后计算 $f(P,K)$。

The input is given from Standard Input in the following format:

$N$ $Q$
$P_1\ P_2\ \dots\ P_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each query is given in the following format:

$x$ $K$

输入从标准输入中按以下格式给出：

$N$ $Q$
$P_1\ P_2\ \dots\ P_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询按以下格式给出：

$x$ $K$

Output $Q$ lines. The $i$-th line should contain the answer to $\mathrm{query}_i$.

输出 $Q$ 行。第 $i$ 行应包含 $\mathrm{query}_i$ 的答案。

Sample 1 Explanation:
For the first query, swapping $P_1$ and $P_2$ gives $P=(3,1,2)$. There are two possible sequences of operations as follows:

• Choose $i = 1$. $P$ becomes $(3,2,1)$. The number of inversions is $3$.
• Choose $i = 2$. $P$ becomes $(1,3,2)$. The number of inversions is $1$.

Thus, the answer is $3+1=4$.

For the second query, swapping $P_2$ and $P_3$ gives $P=(3,2,1)$. There are two possible sequences of operations as follows:

• Choose $i = 1$. $P$ becomes $(3,1,2)$. The number of inversions is $2$.
• Choose $i = 2$. $P$ becomes $(2,3,1)$. The number of inversions is $2$.

Thus, the answer is $2+2=4$.

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• $1 \le x \le N-1$
• $1 \le K \le 10^9$
• All input values are integers.

样例 1 解释：
对于第一个查询，交换 $P_1$ 和 $P_2$ 后得到 $P=(3,1,2)$。存在如下两种可能的操作序列：

• 选择 $i = 1$，则 $P$ 变为 $(3,2,1)$，此时逆序对数量为 $3$；
• 选择 $i = 2$，则 $P$ 变为 $(1,3,2)$，此时逆序对数量为 $1$。

因此，答案为 $3+1=4$。

对于第二个查询，交换 $P_2$ 和 $P_3$ 后得到 $P=(3,2,1)$。存在如下两种可能的操作序列：

• 选择 $i = 1$，则 $P$ 变为 $(3,1,2)$，此时逆序对数量为 $2$；
• 选择 $i = 2$，则 $P$ 变为 $(2,3,1)$，此时逆序对数量为 $2$。

因此，答案为 $2+2=4$。

约束条件

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $P$ 是 $(1,2,\dots,N)$ 的一个排列。
• $1 \le x \le N-1$
• $1 \le K \le 10^9$
• 所有输入值均为整数。