G-区间mex(Hard version)_牛客挑战赛80

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 本题为问题的困难版本，两题的区别在于，本题您需要进行多轮回答，且额外增加了一个修改操作。对于简单版本的题面部分，我们将使用特殊的格式加以标注。

〖引用开始〗

$\hspace{15pt}$ 对于给定的由 $n$ 个整数构成的排列 $\{a_1, a_2, \dots, a_n\}$ ，我们定义 $\operatorname{mex}(i,j)$ 为连续子数组 $\{a_i, a_{i+1}, \dots, a_j\}$ 中最小没有出现过的正整数（其中， $1 \leqq i \leqq j \leqq n$ ）。
$\hspace{15pt}$ 记 $t(i,j) = (j - i + 1) \times \operatorname{mex}(i,j)$ ，求解： $\displaystyle F(a_1,\dots,a_n)=\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n} 2^{t(i,j)} \times t(i,j)$
$\hspace{15pt}$ 由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

〖引用结束〗

$\hspace{15pt}$ 现在，你将会面对 $q$ 次独立询问。第 $k$ 次询问给定数组中的两个元素 $a_i$ 和 $a_j$ ，随后：
$\hspace{23pt}\bullet\,$ 交换 $a_i$ 与 $a_j$ 的位置，得到新的排列 $a'$ ；
$\hspace{23pt}\bullet\,$ 对于 $a'$ ，计算并输出 $F(a')$ 的值。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。
$\hspace{15pt}$ 注意，各次询问相互独立，即每次询问都基于最初给出的原排列。

输入描述:

第一行输入一个整数 ，表示排列的长度。 
第二行输入  个互不相同的整数 ，表示给定的排列。 
第三行输入一个整数 ，表示询问次数。 
此后  行，第  行输入两个整数 ，表示第  次询问。保证  和  均在原数组中出现过。
此外，对于所有询问，保证 。

输出描述:

对于每一次询问，新起一行输出一个整数，表示  对  取模后的结果。

示例1

输入

复制

输出

复制