Contest Duration: - (local time) (100 minutes) Back to Home
Ex - Sequence of Substrings /

Time Limit: 5 sec / Memory Limit: 1024 MB

### 問題文

01 のみからなる長さ N の文字列 S = s_1 s_2 \ldots s_N が与えられます。

• 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}} より辞書順で真に小さい

### 制約

• 1 \leq N \leq 2.5 \times 10^4
• N は整数
• S01 のみからなる長さ N の文字列

### 入力

N
S


### 入力例 1

7
0101010


### 出力例 1

3


K = 3 のとき、例えば (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7) が問題文中の条件を満たします。 実際、s_1 = 0s_3s_4s_5 = 010 より辞書順で真に小さく、s_3s_4s_5 = 010s_6s_7 = 10 より辞書順で真に小さいです。
K \geq 4 のときは、問題文中の条件を満たす \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) は存在しません。

### 入力例 2

30
000011001110101001011110001001


### 出力例 2

9


Score : 600 points

### Problem Statement

You are given a string S = s_1 s_2 \ldots s_N of length N consisting of 0's and 1's.

Find the maximum integer K such that there is a sequence of K pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) that satisfy all three conditions below.

• 1 \leq L_i \leq R_i \leq N for each i = 1, 2, \ldots, K.
• R_i \lt L_{i+1} for i = 1, 2, \ldots, K-1.
• The string s_{L_i}s_{L_i+1} \ldots s_{R_i} is strictly lexicographically smaller than the string s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}}.

### Constraints

• 1 \leq N \leq 2.5 \times 10^4
• N is an integer.
• S is a string of length N consisting of 0's and 1's.

### Input

Input is given from Standard Input in the following format:

N
S


### Sample Input 1

7
0101010


### Sample Output 1

3


For K = 3, one sequence satisfying the conditition is (L_1, R_1) = (1, 1), (L_2, R_2) = (3, 5), (L_3, R_3) = (6, 7). Indeed, s_1 = 0 is strictly lexicographically smaller than s_3s_4s_5 = 010, and s_3s_4s_5 = 010 is strictly lexicographically smaller than s_6s_7 = 10.
For K \geq 4, there is no sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) satisfying the condition.

### Sample Input 2

30
000011001110101001011110001001


### Sample Output 2

9