Problem Description

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 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_1<a_2<\cdots<a_{s-1}<a_s>a_{s+1}>\cdots>a_{n-1}>a_n$.

Your task is to output the answer for every operation.

Input Format

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:

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<<11;
    BASE^=751669;
    BASE^=23465695622566ll;
    return BASE%(n-1)+1;
}

After you finish each query, use the answer of this query $ans$ as the parameter and call Answer(ans) exactly once.

The return value is the $k$ for the next operation.

Note: This input method is only used to reduce the input size. The standard solution does not rely on this input method.

Output Format

Output the answers for all operations, one per line.

4 3
1 5 7 3
1

12
13
13

5 5
7 7 7 7 6
1

9
9
9
9
9

Hint

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.

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