← 返回题目列表

AtCoder · abc240_h

Ex. 子串序列

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个字符串 S = s_1 s_2 \ldots s_N 长度 N 组成 0的和 1的。

求最大整数 K 这样有一个序列 K 整数对 \big((L_1, R_1), (L_2, R_2), \ldots, (L_K, R_K)\big) 满足以下所有三个条件。

  • 1 \leq L_i \leq R_i \leq N 对于每个 i = 1, 2, \ldots, K.
  • R_i \lt L_{i+1} 为 i = 1, 2, \ldots, K-1.
  • 字符串 s_{L_i}s_{L_i+1} \ldots s_{R_i} is 严格按字典顺序较小 比字符串 s_{L_{i+1}}s_{L_{i+1}+1}\ldots s_{R_{i+1}}.

约束

  • 1 \leq N \leq 2.5 \times 10^4
  • N 是一个整数。
  • S 是一个长度为的字符串 N 组成 0的和 1的。

输入

输入由标准输入按以下格式给出:

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 = 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) 满足条件。


示例输入 2

30
000011001110101001011110001001

示例输出 2

9