\(S\) が与えられたとき、\(A_1\) を決定すれば、\(A_2,\ldots,A_{N + 1}\) の値は決まります。\(S\) に対して、条件を満たすような最小の \(A_1\) を持つような \(A\) を対応させることを考えます。

\(S\) の集合は、それを生成する以下のような \(A\) の集合と一対一に対応します。

• \(A\) の奇数番目を取り出した列 \(A_{odd}\) は、広義単調増加である。
• \(A\) の偶数番目を取り出した列 \(A_{even}\) は、広義単調増加である。
• \(A_{odd}\) の先頭要素が \(0\) であるか、\(A_{even}\) の末尾の要素が \(M\) である。

このような \(A\) の集合のサイズは二項係数を用いた式で書くことができます。

計算量は \(O(N + M)\) です。