Median 2

First consider only the prefix records $A$. Define $X_1,X_2,\cdots,X_N$ by

$$X_i=\begin{cases} A_i/2 & (i\text{ is odd}),\\ A_i-X_{i-1} & (i\text{ is even}). \end{cases}$$

If $A_i$ is odd for an odd $i$, or if some $X_i$ is outside $[1,N]$, the answer is impossible.

For odd $i=2k-1$, $X_i$ is the median of the first $i$ elements. After adding one new element, the old median must remain one of the two middle elements of the new set of size $2$. Hence, for even , the two middle elements are exactly and .

This gives an interval $C_i^A$ of values allowed for $P_i$. For $i=1$, we must have . For even , let and . If , then ; if , then . The case is impossible because the two middle values are distinct.

For odd $i\ge 3$, let $l<u$ be the two middle values of the previous even-sized prefix. The new median $X_i$ must lie in $[l,u$. If , then ; if , then ; and if , then . Thus is always one integer interval.

Position restrictions alone are not sufficient. Since $X_i$ is an element already present at time $i$, $\operatorname{pos}(X_i)\le i$. Also, if the two middle elements of an even prefix are , no value strictly between them may have appeared yet. Therefore, for every , . Collecting these restrictions gives one interval for every value .

Why the prefix conditions are sufficient

The conditions above are also sufficient. Proceed by induction on the prefix length. Suppose an odd prefix has median $c$, and the other middle value required at the next even step is $q<c$. The deadline condition guarantees that $q$ has already appeared, while the release conditions guarantee that no value between $q$ and $c$ has appeared. Hence is the element immediately below . Adding a new value makes exactly the two middle values. The case is symmetric.

Process the suffix records $B$ symmetrically from right to left. According to the parity of the suffix length $N-i+1$, define

$$Y_i=\{\begin{array}{ll}{B}_i\mathrm{/}2& (N-i+1\text{ is odd}),\\ B_i-Y_{i+1}& \end{array}$$