概要
解説の貪欲法とは違ったので一応．考察はこちらの方が簡単だという気がする．
解法
$S = (A_1, A_2, \ldots, A_N)$, $P=(1,2,\ldots,N)$ となるように変数変換しておきます（$S$ に対する操作は，最小要素などではなく左端などと読み替えます）．
$i$ 回目の操作終了時点での集合を $S_i$ とすると，$S_i$ は次のものに限定されます：$A_{1+i}$ よりも右の要素は全て残っており，$\{A_1,\ldots,A_{1+i}\}$ のうちちょうど 1 つが $S$ に残っている．
したがって本問題は，次のような状態に関する dp で解くことができます：
- $i$ 回目の操作終了時点で $x\in S$ とすることが可能であるか否かの bool を dp[i][x] と定める．
この dp を適切に高速化しましょう．
$i$ 番目の操作での遷移について考えます．考えるべきは次の 2 点です．
- (1)：dp[i-1][x] が true であるような $x$ について dp[i][x] が false になるかどうかを考える．
- (2)：dp[i][A[1+i]] が true, false どちらであるか否かを考える．
dp[i-1] から dp[i] への変更箇所の $i$ にわたる合計は $N$ 以下（各要素は true から false に 1 回以下変更されるのみ）なので，(1) の変更箇所の列挙と (2) の判定が高速にできれば，dp テーブルの書き変えは in-place にやっていけばよいです．
(1) について考えます．$x$ を $S$ に残したまま $A[1+i]$ を $P$ に挿入できるかどうか考えることになります．すると，$x$ が $A[1+i]$ よりも小さい・大きいかのどちらであるかによって true, false が決まるということが分かります．よって，現在 true となっているような $x$ 全体を set や priority queue などで持っておき，先頭または末尾から順番に辿っていけばすべての false への変更を列挙できます．
(2) について考えます．つまり $A[1+i]$ を集合 $S$ にキープしたまま dp[i][x] が true であるような $x$ を挿入できるかという問題です．これは $x$ を添字とするセグメント木を作って，あるセグメントの中で $A_1, \ldots, A_i$ として現れるものの個数，そのうち $dp[i][x]$ が true であるようなものの個数などを管理すれば求めることができます．
以上を適切に実装すれば $O(N\log N)$ 時間で Yes/No を判定することができます．
Yes の場合の復元については，(2) の計算のついでに 「$x$ を $S$ に残すためには $y$ が $S$ に残しておけばよい」という関係を記録していけばよいです．
