Prefix-Suffix Reconstruction

Once upon a time, Chef had with him an array $A$ of length $N$, with elements in $[1, N]$. From this array $A$, he created a new array $F$ of length $N$ via the following process: - Let $P$ be the prefix maximum array of $A$. That is, $P$ is an array of length $N$ satisfying $P_i = \max(A_1, A_2, \ldots, A_i)$ - Let $S$ be the suffix minimum array of $A$. That is, $S$ is an array of length