시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Byteazar got a string $S$ ($s_1 \dots s_n$) of length $n$ consisting of only digits '0', '1', and '2', and he wants to pick some disjoint subsequences which equal to $2020$, as many as possible.

Formally, Byteazar would like to find $k$ quadruples $(a_1, b_1, c_1, d_1), \dots, (a_k, b_k, c_k, d_k)$  such as

  • $1 \leq a_i < b_i < c_i < d_i \leq n$
  • $s_{a_i} s_{b_i} s_{c_i} s_{d_i} = 2020$
  • $\{a_i, b_i, c_i, d_i\} \cap \{a_j, b_j, c_j, d_j\} = \emptyset$ for $i \neq j$.

Find the maximum value of $k$.

입력

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$). Second line contains the string $S$ ($s_1 \dots s_n$). ($s_i \in \{0, 1, 2\}$). Sum of $n$ in all test cases does not exceed $10^6$.

출력

For each test case print an integer which denotes the result.

예제 입력 1

4
2222
7
2101210
9
122002200

예제 출력 1

0
1
2