P9639 「yyOI R1」youyou 的序列

给定一个长度为 $n$ 的序列 $a_{1\dots n}$，以及 $q$ 次操作。 定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并**立即**询问所有以 $a_i \;( i\in [1,n])$ 为峰的[子序列](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97)数量之和，对 $4294967296$ 取模。**这里的交换是暂时的，也就是说，它仅在下一次操作前有效。** 在此我们认为，一个长度至少为 $1$ 的序列 $[a_1,a_2 ,\cdots,a_{s-1},a_s,a_{s+1},\cdots,a_{n-1},a_n ]$，满足 $a_1a_n$，则称此序列为以 $a_s$ 为峰的序列。 你的任务是回答出所有操作的答案。

第一行输入两个整数 $n,q$。 第二行输入 $n$ 个正整数，表示一开始的序列 $a_{1\dots n}$。 第三行，输入一个整数 $k$，表示进行第一次操作（定义见上），保证 $1\le k >7; BASE=BASE

你需要输出所有操作的答案，每个答案输出一行。

### 样例解释 #1 第一次操作的 $k$ 为 $1$。 此时序列为 $[5,1,7,3]$。 峰为 $a_1$：$[5]$，$[5,1]$，$[5,3]$。 峰为 $a_2$：$[1]$。 峰为 $a_3$：$[7]$，$[5,7]$，$[1,7]$，$[7,3]$，$[5,7,3]$，$[1,7,3]$。 峰为 $a_4$：$[3]$，$[1,3]$。 共计 $12$ 个不同的子序列，答案输出 $12$。 第二次和第三次操作的 $k$ 均为 $3$ ，此时有 $13$ 个不同的序列满足条件。 ### 样例解释 #2 第一次操作的 $k$ 为 $1$。 此时序列为 $[7,7,7,7,6]$。 峰为 $a_1$：$[7]$，$[7,6]$。 峰为 $a_2$：$[7]$，$[7,6]$。 峰为 $a_3$：$[7]$，$[7,6]$。 峰为 $a_4$：$[7]$，$[7,6]$。 峰为 $a_5$：$[6]$。 共计 $9$ 个不同的子序列，答案输出 $9$。 后四次操作同理。 --- ### 数据范围 **本题采用捆绑测试。** | 子任务编号 | $n$ | $q$ | 分数 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le 500$ | $\le 100 $ |$10$ | | $2$ | $\le2\times10^3$|$ \le 5\times10^3$ | $20$ | | $3$ | $\le3\times10^4$ |$\le 10^4$ | $30$ | | $4$ | $\le10^6$|$ \le10^6$ | $40$ | 对于 $100\%$ 的数据，$2\le n\le10^6$，$1\le q\le10^6$，$1\le a_i\le10^4$。