题目描述

$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$

输出格式

答えを出力せよ。

题目大意

给定一个长度为 $n$ 的 $01$ 串，求最多可以选出多少互不相交的子串，满足这些子串按照原串中的顺序，字典序严格升序。

7
0101010

3

30
000011001110101001011110001001

9

提示

制約

• $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) $ は存在しません。