20789번 - Build More 2020's! 다국어

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.