Antiamuny and Slider Movement

The $q!$ permutations look terrifying, but the monster is fake. The trick is to stop simulating sliders and start asking threshold questions.

Compress The Coordinates

Let the actual position of slider $i$ be $p_i$. Define

$b_i=p_i-i$.

Because $p_1<p_2<\dots<p_n$, the array $b$ is nondecreasing. Also every value lies in $[0,m-n]$. Let

$M=m-n$.

For an operation $(i,x)$, define its compressed target as

$y=x-i$.

Now look at what this operation does to $b$.

If slider $i$ moves right, then every slider to its right that is too far left gets pushed until its compressed value is at least $y$. If it moves left, every slider to its left that is too far right gets pushed until its compressed value is at most $y$.

Because $b$ is sorted, both cases combine into one clean formula:

• for $j<i$: $b_j=\min(b_j,y)$
• for $j=i$: $b_j=y$
• for $j>i$: $b_j=\max(b_j,y)$

That is the first big simplification. The slider physics was just a dramatic way to say prefix-min, point-assign, suffix-max.

Fix One Slider

Now fix a slider $k$. We only care about the scalar value $b_k$.

Each operation $(i,y)$ acts on this scalar as:

• if $i<k$, then $b_k=\max(b_k,y)$
• if $i=k$, then $b_k=y$
• if $i>k$, then $b_k=\min(b_k,y)$

A direct expected value DP over these max/min/assign operations is annoying. Max and min do not commute; trying to average them directly is where solutions go to die.

So do not average the value directly. Average its bits by threshold.

For an integer value $v$ in $[0,M]$,

$v=\sum_{t=1}^{M} [v\ge t]$.

So if we can compute $P(b_k\ge t)$ for every useful threshold $t$, we can sum those probabilities to get the expected compressed position.

The Threshold Bit

Fix slider $k$ and threshold $t$. Track the boolean

$B=[b_k\ge t]$.

Now classify an operation $(i,y)$:

• If $i<k$, it applies $\max(b_k,y)$. This forces $B$ to true exactly when $y\ge t$.
• If $i=k$, it assigns $b_k=y$. This forces true if $y\ge t$, false if $y<t$.
• If $i>k$, it applies $\min(b_k,y)$. This forces $B$ to false exactly when $y<t$.

So the true-forcing operations are exactly:

$(i\le k \text{ and } y\ge t)$

and the false-forcing operations are exactly:

$(i\ge k \text{ and } y<t)$.

Let

$A=$ number of true-forcers,

$C=$ number of false-forcers.

If $A+C=0$, no operation ever touches this threshold bit, so it stays equal to the initial value $[b_k\ge t]$.

Otherwise, in a uniformly random permutation, the last forcing operation is uniformly distributed among those $A+C$ forcing operations. If the latest one is a true-forcer, the final bit is true; if it is a false-forcer, the final bit is false. Irrelevant operations after it do nothing to this bit.

Therefore

$P(b_k\ge t)=\frac{A}{A+C}$

when $A+C>0$.

That is the whole combinatorics trick. No factorial explosion, no cursed permutation DP.

Sweeping Thresholds

For fixed $k$, the values $A$ and $C$ only change when $t$ passes some operation target $y$.

An operation with target $y$ contributes:

• to $A$ while $t\le y$, if its index is $\le k$
• to $C$ while $t>y$, if its index is $\ge k$

So sort all operations by $y$, then sweep threshold intervals. On an interval where no target is crossed, $A$ and $C$ are constant, so the probability is constant too. Add interval length times that probability.

If $A+C=0$ on an interval, add only the part of the interval where the initial $b_k$ is at least $t$.

This gives the expected compressed final value of slider $k$ modulo $10^9+7$.

Finally, actual position is $k+b_k$, and the answer asks for the sum over all $q!$ permutations, so multiply the expected position by $q!$.

Complexity

For each slider, we scan the sorted operation targets once. That is $O(nq)$ per test case after sorting, with $O(n+q)$ memory. Since the total $n$ and total $q$ are both at most $5000$, this is comfortably fine.