AT_abc240_h [ABC240Ex] Sequence of Substrings

[problemUrl]: https://atcoder.jp/contests/abc240/tasks/abc240_h $ 0 $ と $ 1 $ のみからなる長さ $ N $ の文字列 $ S\ =\ s_1\ s_2\ \ldots\ s_N $ が与えられます。 整数の $ 2 $ つ組を $ K $ 個並べた列 $ \big((L_1,\ R_1),\ (L_2,\ R_2),\ \ldots,\ (L_K,\ R_K)\big) $ であって以下の $ 3 $ つの条件をすべて満たすものが存在するような最大の整数 $ K $ を出力してください。 - $ i\ =\ 1,\ 2,\ \ldots,\ K $ について、$ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ i\ =\ 1,\ 2,\ \ldots,\ K-1 $ について、$ R_i\ \lt\ L_{i+1} $ - $ i\ =\ 1,\ 2,\ \ldots,\ K-1 $ について、文字列 $ s_{L_i}s_{L_i+1}\ \ldots\ s_{R_i} $ は文字列 $ s_{L_{i+1}}s_{L_{i+1}+1}\ldots\ s_{R_{i+1}} $ より**辞書順で真に小さい**

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2.5\ \times\ 10^4 $ - $ N $ は整数 - $ S $ は $ 0 $ と $ 1 $ のみからなる長さ $ N $ の文字列 ### Sample Explanation 1 $ K\ =\ 3 $ のとき、例えば $ (L_1,\ R_1)\ =\ (1,\ 1),\ (L_2,\ R_2)\ =\ (3,\ 5),\ (L_3,\ R_3)\ =\ (6,\ 7) $ が問題文中の条件を満たします。 実際、$ s_1\ =\ 0 $ は $ s_3s_4s_5\ =\ 010 $ より辞書順で真に小さく、$ s_3s_4s_5\ =\ 010 $ は $ s_6s_7\ =\ 10 $ より辞書順で真に小さいです。 $ K\ \geq\ 4 $ のときは、問題文中の条件を満たす $ \big((L_1,\ R_1),\ (L_2,\ R_2),\ \ldots,\ (L_K,\ R_K)\big) $ は存在しません。