You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明出题出累了，去搬了一道题。

给你一个01串，长度是$N$。

你需要从中切出$k$个区间$[L_i,R_i]$满足：

（1）$R_i<L_{i+1}$，对所有$1\leq i<k$成立。

（2）$S_{[L_i,R_i]}<S_{[L_{i+1},R_{i+1}]}$对所有$1\leq i<k$成立。

问，最大的$k$是多少？

输入格式

第一行输入$N$。

第二行输入一个长度为$N$的$01$串。

输出格式

输出一个数字表示答案。

7
0101010

3

30
000011001110101001011110001001

9

data3.in
data3.out data4.in
data4.out
data5.in
data5.out

数据范围

对于10%的数据：$N\leq 20$。

对于40%的数据：$N\leq 100$。

对于60%的数据：$N\leq 1500$。

对于100%的数据：$N\leq 2.5\times 10^4$。