Median Permutation

Use 0-indexed positions. Put a directed edge $u -> v$ to mean $p_u < p_v$.

First, get rid of a tempting but useless idea: do not try to DP the medians directly. The medians are a symptom. The real structure is in the order relations between positions.

There are $n-2$ medians, and neither $1$ nor $n$ can ever be a median. Therefore, if all medians are distinct, then $f(p)$ is exactly the set $2,3,...,n-1$.

Now two local facts do basically all the work.

First, if $f_i=f_j$, the equal value appears in both triples, so the triples must share its position. Thus $|i-j| <= 2$. Any duplicate median is visible inside some length-$5$ block.

Second, consider a center $i$ with both $i-2$ and $i+2$ present. If

$p_{i-2} < p_i > p_{i+2}$,

then $p_i$ must be $n$. Suppose not. If $p_{i+1} > p_i$, then the triple $(i,i+1,i+2)$ has median $p_i$. To avoid also making $(i-1,i,i+1)$ have median $p_i$, we need $p_{i-1} > p_i$. But then $(i-2,i-1,i)$ has median $p_i$ anyway. Same argument from the other side. So both neighbors $p_{i-1}$ and $p_{i+1}$ must be smaller than $p_i$, meaning $p_i$ is never a median in any triple containing it. Since $p_i$ is not $1$ or $n$, impossible. Hence $p_i=n$. The valley case is symmetric: if $p_{i-2} > p_i < p_{i+2}$, then $p_i=1$.

So along each parity, the comparisons can only turn at the positions of $1$ and $n$. That is already a huge collapse.

We also need to understand how the two parities compare. For four consecutive positions with values $A,B,C,D$, suppose $A<C$ and $B>D$. The two triples are $(A,B,C)$ and $(B,C,D)$. A short rank check gives only two valid orders:

• $A<C<D<B$
• $D<B<A<C$

In plain English: when one parity rises and the other falls, one whole parity-pair must sit below the other. No partial crossing allowed. Crossings are how duplicate medians sneak in and ruin your day.

Now assume the position of $1$ is before the position of $n$; if not, reverse the whole array. Reversal is a bijection and preserves the distinctness condition.

Build the forced inequality graph like this.

If pos1 and posn have the same parity:

• on the opposite parity, add edges left-to-right: $i-2 -> i$;
• on their parity, add edges moving away from $1$ on the left: $i+2 -> i$;
• between $1$ and $n$, add $i-2 -> i$;
• after $n$, add $i -> i-2$.

If pos1 and posn have different parity:

• on the parity of $1$, add edges away from $1$ on both sides;
• on the parity of $n$, add edges toward $n$ on both sides.

Finally add the two bridge inequalities forced by the four-position rule near the ends:

• if pos1 != 0, add $0 -> 1$ when pos1 is even, otherwise $1 -> 0$;
• if posn != 0, add $n-2 -> n-1$ when posn has the same parity as $n-1$, otherwise $n-1 -> n-2$.

Then remove the outgoing edge from the actual position of $1$, and remove every edge going into the actual position of $n$. We treat $1$ and $n$ as virtual endpoints, not normal chain elements.

The graph becomes at most two increasing chains. Every valid permutation must respect these chains by the local facts above. Conversely, if values increase along these chains, every length-$5$ window has one of the valid local rank patterns, so no duplicate median appears. Since duplicates are local, that is sufficient.

Now counting is clean.

Once we know which values belong to each chain, the actual placement is forced: each chain receives its chosen values in increasing order. So the only choice is the chain membership of each currently unknown value.

During chain traversal, store where[x] = (chain, index) for each fixed value $x$. Also store virtual $1$ as the first element of chain $1$, and virtual $n$ as the element after the last real element of the last chain.

For a fixed left value $x$, define left as the number of values in chain $1$ among $1..x$:

• if $x$ is in chain $1$ at index $c$, then left = c+1;
• if $x$ is in chain $2$ at index $c$, then left = x-(c+1).

For the next fixed value $y$, define right as the number of values in chain $1$ among $1..y-1$:

• if $y$ is in chain $1$ at index $c$, then right = c;
• if $y$ is in chain $2$ at index $c$, then right = y-1-c.

The values $x+1,...,y-1$ are all unfixed. There are $y-x-1$ of them, and exactly right-left must go to chain $1$. So this gap contributes

$C(y-x-1, right-left)$.

Multiply this over all consecutive fixed values. If a fixed constraint is impossible, the binomial has an invalid lower argument and contributes $0$.

Edge cases are handled naturally: no unknown values means all gaps have size $0$; adjacent $1$ and $n$ may produce only one real chain; fixed values contradicting the chain order produce answer $0$.

Precompute factorials and inverse factorials. The graph construction and counting are linear, so the total complexity is $O(n)$ per test case after precomputation, with $O(n)$ memory.