Balance

The palindrome shortcut

First, notice the invariant: the array is always a palindrome.

• Empty array: palindrome.
• Type 2 turns $[a_1,\ldots,a_n]$ into $[x,a_1,x,a_2,\ldots,x,a_n,x]$. If the old array was a palindrome, the new one is too.
• Type 1 deletes the middle element of a palindrome, which still leaves a palindrome.

That invariant is the whole reason this problem is not complete nonsense.

Take any non-empty subsequence of length $m$, with values in chosen order $v_1,v_2,\ldots,v_m.$ Its balance is $B=\frac{1v_1+2v_2+\cdots+mv_m}{m}.$

Now mirror the chosen positions across the palindrome. The chosen values appear in reverse order: $v_m,v_{m-1},\ldots,v_1.$ The mirrored balance is $B'=\frac{1v_m+2v_{m-1}+\cdots+mv_1}{m}.$

Add them: $B+B'=\frac{(m+1)(v_1+\cdots+v_m)}{m}.$

So $B+B'=\sum v_i+\frac{\sum v_i}{m}.$

Since mirroring is a bijection on all subsequences, summing over all subsequences gives $2\cdot \text{answer}=A+C,$ where:

• $A$ is the sum of element-sums over all non-empty subsequences,
• $C$ is the sum of ordinary averages over all non-empty subsequences.

Computing $A$

Let $S=\sum_{i=1}^n a_i.$

Each element appears in exactly $2^{n-1}$ subsequences, so $A=2^{n-1}S.$

Computing $C$

Fix one element $a_i$. In subsequences of length $k$, it appears in $\binom{n-1}{k-1}$ ways, and contributes $a_i/k$ to the average.

So its total coefficient in $C$ is $\sum_{k=1}^n \frac{1}{k}\binom{n-1}{k-1}.$

Use $\frac{1}{k}\binom{n-1}{k-1}=\frac{1}{n}\binom{n}{k}.$

Therefore $\sum_{k=1}^n \frac{1}{k}\binom{n-1}{k-1}=\frac{2^n-1}{n}.$

Thus $C=\frac{2^n-1}{n}S.$

So the answer is $\boxed{\frac{S}{2}\left(2^{n-1}+\frac{2^n-1}{n}\right)}.$

The statement guarantees $n\not\equiv 0\pmod M$ on type 3 queries, so division by $n$ is legal modulo $M=10^9+7$.

Maintaining the easy stuff

Maintain:

• $S\bmod M$,
• $n\bmod M$,
• $p=2^n\bmod M$,
• the parity of the real length.

For type 2 with value $x$: $n'=2n+1,$ $S'=S+(n+1)x,$ $2^{n'}=2^{2n+1}=2(2^n)^2.$

For type 1, after removing value $v$: $n'=n-1,$ $S'=S-v,$ $2^{n'}=2^n/2.$

So the math part is tiny. The real trap is: what is $v$?

Finding the deleted middle value

Do not assume the newest inserted $x$ is the middle. That is just wrong. Example:

$[1]\xrightarrow{\text{insert }2}[2,1,2],$

and the middle is still $1$, not $2$.

For every type 2 insertion, store its value and a state in $\{0,1,2,3\}$.

Interpret the states like this:

• state $0$ or $1$: this insertion supplies the current deleted middle value;
• state $2$ or $3$: this insertion is skipped, so we look at older insertions.

Whenever a type 1 deletion touches an insertion, advance its state: $s\leftarrow (s+1)\bmod 4.$

Now, what initial state should a new insertion get?

If the old length is even, the inserted $x$ goes exactly in the middle, so it should be deleted immediately. Start at state $1$: $\text{take},\text{pass},\text{pass},\text{take},\text{take},\ldots$

If the old length is odd, the old middle survives as the new middle, and the inserted $x$ appears for the next two deletions. Start at state $3$: $\text{pass},\text{take},\text{take},\text{pass},\text{pass},\ldots$

For a type 1 query, scan insertions from newest to oldest:

• advance the state;
• if the old state was $0$ or $1$, return this value;
• otherwise continue.

This is amortized $O(1)$: the state machine behaves like a small carry chain, and over the whole query stream the total number of passed states is linear. No giant array, no cursed rope structure, no suffering for sport.

Complexity

Each query costs amortized $O(1)$ except modular inverse on type 3, which costs $O(\log M)$.

Total complexity: $O(q\log M)$ with $O(q)$ memory.