恐ろしい新病 COWVID-19 が世界の牛に広がります。Farmer John は群れを感染から守るため可能な予防をします。

細長い納屋に $N$ 房（$2 \leq N \leq 10^5$）、一部牛、一部空。社会的距離の重要性を読み $D$ を最大化。$D$ は最も近い二占有房の距離。3と8が最も近ければ $D = 5$。

新しい二頭を以前空の房へ置き $D$ 最大に。既存牛は移動不可、新牛だけ割当て。

入力

初行 $N$、次は長さ $N$ の01列、0空1占有。少なくとも二0、二頭の場所あり。

出力

二頭の最適配置後の最大 $D$、最も近い占有房の距離。

入出力例

入力 1

14
10001001000010

出力 1

2

注記

10x010010x0010 とでき、xが新牛。$D = 2$、これ以上の $D$ は不可能。

小課題

• テスト2–6は $N\le 10$。
• テスト7–8は $N\le 100$。
• テスト9–11は $N \le 5000$。
• テスト12–15追加条件なし。

問題作成者：Brian Dean