Array and Permutation

Research check: the official Codeforces Round 1079 editorial page for 2197B includes solution code that stores each value's position in $p$ and rejects exactly when these positions decrease while scanning $a$. Public OK submissions are listed for the same problem on cf-problemset. The supplied statement is still canonical.

Let $pos[x]$ be the index where value $x$ appears in the original permutation $p$. Since $p$ is a permutation, this is well-defined for every $1 \le x \le n$.

Instead of tracking the values themselves, track their origin labels. The value $x$ has origin label $pos[x]$. Initially, the origin-label array is

$[1,2,3,\ldots,n].$

If the final array is $a$, then its origin-label sequence must be

$b_i = pos[a_i].$

So the question becomes: starting from $[1,2,\ldots,n]$, which arrays of origin labels can be made by repeatedly copying one adjacent label into the other?

The answer is exactly the nondecreasing ones.

First, necessity. Initially the origin labels are nondecreasing. Suppose adjacent labels are $x \le y$. Copying left to right makes the pair $(x,x)$; copying right to left makes it $(y,y)$. Either way, no inversion appears. So if for some $i$,

$pos[a_i] > pos[a_{i+1}],$

then the target is impossible. No amount of adjacent-copy button mashing fixes that.

Now sufficiency. We prove by induction that every nondecreasing sequence $b$ with values in $[1,n]$ can be generated from $[1,2,\ldots,n]$.

For $n=1$, trivial. For larger $n$, every nondecreasing map has a fixed point: some $j$ with $b_j=j$. Take the smallest $j$ such that $b_j \le j$. This exists because $b_n \le n$. If $j=1$, then $b_1=1$. Otherwise, $b_{j-1}>j-1$, so $b_{j-1}\ge j$; monotonicity gives $b_j\ge j$, and together with $b_j\le j$, we get $b_j=j$.

Because $b$ is nondecreasing and $b_j=j$, the prefix $1\ldots j$ only needs labels from $1\ldots j$, and the suffix $j\ldots n$ only needs labels from $j\ldots n$. By induction, build the prefix using only that prefix. Then position $j$ is label $j$, and positions after $j$ are untouched. Shift the suffix labels by $j-1$ and apply induction again on positions $j\ldots n$. The two constructions only overlap at $j$, whose final label is still $j$.

So the invariant is not merely necessary; it is the full characterization.

Implementation:

1. Store $pos[p_i]=i$.
2. Scan $a$ left to right.
3. If $pos[a_i]$ ever decreases, print NO; otherwise print YES.

Do not assume a value's original position must lie inside its final block. Sample 6 kills that false idea: value $2$ starts at position $3$ but ends at positions $1,2$, and the answer is YES.

Complexity is $O(n)$ per test case and $O(n)$ memory. Across all tests, this is $O(\sum n)$.