Revival

Front-to-back greedy is the trap here. Picking some value that satisfies the current prefix can easily wreck a future fixed p, so we solve the permutation backwards.

Define

$A_i = i(i-1)/2 - s_i$.

So $A_i$ is the number of increasing pairs inside prefix $i$. This is nicer than inversions because if position $i$ is currently the last remaining position, then the new contribution of $p_i$ is exactly the number of previous elements smaller than $p_i$.

The reverse operation is clean: once we decide the last element, delete it. Values greater than it would all decrease by $1$ in the smaller permutation, but prefix inversion counts before it do not change, because relative order inside those prefixes does not change. We do not actually mutate all values. Instead, keep a Fenwick tree over original labels that tells us which values are still alive. Ranks among alive values behave exactly like the decreased values would.

Now process only the positions marked s, from right to left.

Let r be the current s position, and let l be the previous s position, or $0$ if there is none. The positions $l+1,\dots,r-1$ are all fixed p positions; call this block $B$. Before processing r, our Fenwick tree contains exactly the values used in prefix $r$, each with weight $1$. Any fixed suffix after the last s was deleted before the loop starts.

Let $x=p_r$, let $E$ be the first $l$ positions, and let $m=|B|$. Also let

$D=A_r-A_l$.

This $D$ counts all increasing pairs whose right endpoint is in $B$ or at position $r$.

We scan the fixed block $B$ from right to left. When we are at a fixed position $j$, all fixed block positions to its right have already been deleted from the Fenwick tree. So

$q_j = \text{number of alive values smaller than } p_j$

counts the real increasing-pair contribution of position $j$, plus one possible fake extra count: the unknown value $x$, if $x<p_j$. Therefore, after summing all these queries into $Q$,

$Q = \text{contribution of the fixed block} + \text{number of block values greater than }x$.

The contribution of $x$ itself is

$L_E(x)+L_B(x)$,

where $L_E(x)$ is the number of values in $E$ smaller than $x$, and $L_B(x)$ is the number of values in $B$ smaller than $x$. Since every block value is either smaller or greater than $x$,

$D-Q+m = L_E(x)+2L_B(x)$.

That is the whole trick. After the scan, the Fenwick tree contains the earlier prefix $E$ and the unknown value $x$ with weight $1$, while the fixed block has weight $0$. Temporarily add weight $2$ to every value in $B$. Now the total weight strictly below $x$ is exactly

$K=D-Q+m$.

Since $x$ itself still has weight $1$, the value at zero-based weighted rank $K$ is exactly $x$. Find it with a Fenwick kth query, store it as $p_r$, undo the temporary weights, and delete $x$.

The invariant is then restored for the previous s position: the Fenwick tree contains exactly the values of the remaining prefix. No backtracking, no guessing, no nonsense.

Edge cases:

• If there is no s position, every value is directly fixed; output them.
• For the first s position, use $l=0$ and $A_0=0$.
• Fixed positions after the last s are deleted before processing starts.

Each fixed position is touched only inside its own segment, and each s position does one kth query. So the complexity is $O(n \log n)$ per test case, with $O(n)$ memory.