QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3761. 2020

统计

Bobo 有一个只包含数字 0, 1, 2 的,长度为 n 的字符串 s1sn。他想选出最多的互不重叠的连续子串,这些子串都是 2020. 求最多可以选出的子串数量。

形式化地,他想要求出最大的 k, 使得存在 k 个下标 i1,,ik 满足

  • sitsit+1sit+2sit+3=2020
  • 对于 1t<k, 满足 it+4it+1

Input

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含一个整数 n,第二行包含一个字符串 s1sn.

  • 1n105
  • si{0,1,2}
  • n 的和不超过 106.

Output

对于每组数据,输出一个整数,表示所求的值。

样例输入

4
2020
6
202020
10
1202012020

样例输出

1
1
2