以下、 \(X = (1, 2, \dots ,N)\) であるとします。

まず操作について考えます。操作をする順番は操作可能性や残る点集合に影響を与えないことから、操作をする点集合のみが重要です。点集合 \(s\) に属する全ての点に対して操作をできる条件は、以下の通りです。

• \(s\) に属する点を昇順に並び替えた列を \(s' = (s'_1, s'_2, \dots ,s'_m)\) として、 \(Y_{s'_1} > Y_{s'_2} > \dots > Y_{s'_m}\) を満たす。

点集合 \(s\) に属する全ての点に対して操作をしたとき、ある点 \(i\) が残る条件は、以下の通りです。

• \(s \cup \{i\}\) に属する点を昇順に並び替えた列を \(t = (t_1, t_2, \dots ,t_m)\) として、 \(Y_{t_1} > Y_{t_2} > \dots > Y_{t_m}\) を満たす。

答えを直接求めようとすると難しいので、操作をする点集合のうち極大なものを数えます。具体的には、点集合 \(s\) であって、以下を満たすようなものを数えます。

• \(s\) に属する全ての点に対して操作可能である
• \(s\) に属する全ての点に対して操作をした後、他の点に操作をすると必ず \(1\) つ以上の点が消える

極大な操作点集合と操作後に残る可能性のある点集合は一対一対応します。極大な操作点集合は、累積和を用いて最悪計算量が \(O(N^3)\) の DP で数え上げられます。工夫すればもう少し改善できます。実装例