2020 더 만들기!

Byteazar는 '0', '1', '2'로만 이루어진 길이 $n$의 문자열 $S$ ($s_1 \dots s_n$)를 받았고, 여기서 $2020$과 같은 서로 겹치지 않는 부분수열을 최대한 많이 고르려고 한다.

형식적으로 Byteazar는 다음 조건을 만족하는 $k$개의 네 쌍 $(a_1, b_1, c_1, d_1), \dots, (a_k, b_k, c_k, d_k)$를 찾으려 한다.

• $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$
• $i \neq j$일 때 $\{a_i, b_i, c_i, d_i\} \cap \{a_j, b_j, c_j, d_j\} = \emptyset$

$k$의 최댓값을 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝에서 끝난다.

각 테스트 케이스의 첫째 줄에는 정수 $n$이 주어진다. ($1 \le n \le 10^5$) 둘째 줄에는 문자열 $S$ ($s_1 \dots s_n$)가 주어진다. ($s_i \in \{0, 1, 2\}$) 모든 테스트 케이스에서 $n$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 결과를 나타내는 정수를 한 줄에 출력한다.