Counting Mountain Subsequences with Temporary Swap

Given an array \(a_{1\dots n}\) of length \(n\) consisting of distinct integers, and \(q\) operations. In each operation, you are given an index \(k\) (1-indexed); temporarily swap \(a_k\) and \(a_{k+1}\), and then immediately answer the following query before reverting the array to its original state.

The query is: For every index \(i\) (\(1 \le i \le n\)), consider all subsequences (with the original order preserved; note that a subsequence is not necessarily contiguous) which have \(a_i\) as the peak. We say that a subsequence \[ [a_1, a_2, \dots, a_{s-1}, a_s, a_{s+1}, \dots, a_n] \] (with length at least 1) is a mountain subsequence with peak \(a_s\) if it satisfies \[ a_1 < a_2 < \cdots < a_{s-1} a_{s+1} > \cdots > a_n. \] An empty left part or empty right part is allowed (so a subsequence consisting of a single element qualifies).

For each operation, after performing the temporary swap, you must compute the sum over all indices \(i\) of the number of mountain subsequences that have \(a_i\) as the peak. Since this number can be huge, output the answer modulo \(4294967296\) (i.e. \(2^{32}\)).

Note: The swap is temporary – it is only effective for the current operation, and the array reverts to its original ordering before the next operation.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le \text{small})\) representing the length of the array and the number of operations respectively.

The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\). It is guaranteed that the \(a_i\)'s are distinct.

Each of the following \(q\) lines contains a single integer \(k\) \((1 \le k < n)\) indicating that in this operation you temporarily swap \(a_k\) and \(a_{k+1}\).

outputFormat

For each operation, output a single line containing one integer – the sum over all \(i\) of the counts of mountain subsequences with peak \(a_i\) computed on the temporarily modified array, modulo \(4294967296\).

sample

3 2
1 2 3
1
2

6
7