P9639 "yyOI R1" youyou's Sequence

You are given a sequence $a_{1\dots n}$ of length $n$, and $q$ operations. One operation is defined as: swap the values of $a_k$ and $a_{k+1}$, and **immediately** ask for the sum of the numbers of [subsequences](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97) that have $a_i \;( i\in [1,n])$ as the peak, modulo $4294967296$. **This swap is temporary, meaning it is only valid until the next operation.** Here we consider that a sequence of length at least $1$, $[a_1,a_2,\cdots,a_{s-1},a_s,a_{s+1},\cdots,a_{n-1},a_n]$, is called a sequence with peak at $a_s$ if it satisfies $a_1a_n$. Your task is to output the answer for every operation.

The first line contains two integers $n,q$. The second line contains $n$ positive integers, the initial sequence $a_{1\dots n}$. The third line contains an integer $k$, meaning the first operation (as defined above) is performed, and it is guaranteed that $1\le k < n$. --- For operations $2$ to $q$, the value of $k$ is obtained as follows: ```cpp int Answer(unsigned int ans) { unsigned int BASE=998244353ll*ans+ans*ans+ans/9991+ans%2159; BASE^=9810; BASE^=51971; BASE=BASE>>7; BASE=BASE

Output the answers for all operations, one per line.

### Sample Explanation #1 For the first operation, $k$ is $1$. Now the sequence is $[5,1,7,3]$. Peak at $a_1$: $[5]$, $[5,1]$, $[5,3]$. Peak at $a_2$: $[1]$. Peak at $a_3$: $[7]$, $[5,7]$, $[1,7]$, $[7,3]$, $[5,7,3]$, $[1,7,3]$. Peak at $a_4$: $[3]$, $[1,3]$. In total there are $12$ different subsequences, so the answer is $12$. For the second and third operations, $k$ is both $3$. At this time there are $13$ different sequences that satisfy the condition. ### Sample Explanation #2 For the first operation, $k$ is $1$. Now the sequence is $[7,7,7,7,6]$. Peak at $a_1$: $[7]$, $[7,6]$. Peak at $a_2$: $[7]$, $[7,6]$. Peak at $a_3$: $[7]$, $[7,6]$. Peak at $a_4$: $[7]$, $[7,6]$. Peak at $a_5$: $[6]$. In total there are $9$ different subsequences, so the answer is $9$. The last four operations are similar. --- ### Constraints **This problem uses bundled testdata.** | Subtask ID | $n$ | $q$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $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$ | For $100\%$ of the testdata, $2\le n\le10^6$, $1\le q\le10^6$, $1\le a_i\le10^4$. Translated by ChatGPT 5