文字列 \(S\) を 1 で区切って各区間に 0 が何個あるかを表した整数列 \(A\) を考えます。端に 1 がある場合も、\(A\) の端に \(0\) が存在すると考えます。

例えば、\(S=\) 1001101000 のとき、 \(A=(0,2,0,1,3)\) です。

問題文の操作は、数列 \(A\) に対して以下の操作を行うことに対応します。

• \(A\) の中に含まれる端以外の \(0\) を削除する。
• \(A\) の中で隣接する \(2\) つであってどちらも \(1\) 以上のものを選び、両方の値を \(1\) 減らす。

最終的な \(A\) の状態を考えます。 操作回数の最大化をするために、最終的な \(A\) の要素の総和の最小化を考えます。 \(A\) に対して操作が行えないのは、正整数が \(1\) つ以下の場合です。 ここで、\(A\) の要素の総和を \(x\)、 最大値を \(m\) とします。 \(m \le \frac{x}{2}\) かつ \(x\) が偶数のとき、\(A\) の全ての要素を \(0\) にすることができます。 \(m \le \frac{x}{2}\) かつ \(x\) が奇数のとき、最後に \(1\) が \(1\) つ残ります。 \(m > \frac{x}{2}\)の場合は最大値である正整数が \(1\) つ残ります。