Bobo 有一个只包含数字 0, 1, 2 的,长度为 n 的字符串 s1…sn。他想选出最多的互不重叠的连续子串,这些子串都是 2020. 求最多可以选出的子串数量。
形式化地,他想要求出最大的 k, 使得存在 k 个下标 i1,…,ik 满足
- sitsit+1sit+2sit+3=2020
- 对于 1≤t<k, 满足 it+4≤it+1
Input
输入文件包含多组数据,请处理到文件结束。
每组数据的第一行包含一个整数 n,第二行包含一个字符串 s1…sn.
- 1≤n≤105
- si∈{0,1,2}
- n 的和不超过 106.
Output
对于每组数据,输出一个整数,表示所求的值。
样例输入
4 2020 6 202020 10 1202012020
样例输出
1 1 2