各 \(1 \leq v \leq N\) について，最終的に \(s\) に含まれる \(v\) 以上の値の個数の最大化，を考えてみます．

これは，\(i\) 回目の push で \(i\) を入れる，というのが最適解だとわかります．

この戦術は \(v\) に依りません． この解で得られる \(s\) を，\(Z=\{Z_1 < Z_2 < \cdots < Z_K\}\)（\(K=A-B\)）と置きます．

\(x=\{x_1< x_2 < \cdots < x_K\}\) を \(s\) として残すことができるかどうかを考えます． まず，\(x_i \leq Z_i\) \((1 \leq i \leq K\))が必要です． そうでないとすると，ある \(v\) が存在して，\(v\) 以上の値の個数が \(Z\) よりも \(x\) の方が多くなるためです．

この必要条件は実は十分です． これさえわかれば，条件を満たす \(x\) の個数は簡単な \(O(A^2)\) 時間 DP で求めることができます．

最後に，十分性を示します． 以下のように push を行えばよいです．

• \(1 \leq i \leq N\) であって，\(Z\) に含まれない \(i\) の集合を，\(W=\{W_1<W_2<\cdots<W_{B}\} \) とおく．
• \(1 \leq i \leq N\) であって，\(x\) に含まれない \(i\) の集合を，\(y=\{y_1<y_2<\cdots<y_{B}\} \) とおく．
• \(Z_i\) 回目の push では \(x_i\) を push する．
• \(W_i\) 回目の push では \(y_i\) を push する．

\(W_i \leq y_i\) が成立することに注意すると，この戦術が実際に解となっていることがわかります．