This page is still under construction.

Parts of this page are still being built. What you see may change.

Count Down Up 2020

Interview

Time limit2sMemory limit512 MB

Summary
Given lists of digits, count how many times the consecutive subsequence 2, 0, 2, 0 appears, including overlaps.
Level

Easy2 of 10

Topics
Array, Implementation, Brute force
Solved
No attempts yet

Problem

The countdown to the Olympic and Paralympic Games Tokyo 2020 continues until summer 2021. That aside, you are asked to count up the occurrences of the four integers 2, 0, 2, and 0 appearing consecutively in this order in given lists of integers.

Input

The input consists of multiple datasets, each in the following format.

n d1 … d**n

Each of the datasets consists of two lines. The first line has an integer n (4 ≤ n ≤ 1000), which is the number of integers listed in the second line. The second line contains n integers d1, …, dn separated by spaces. Here, all of d1 to dn are between 0 and 9, inclusive.

The end of the input is indicated by a line containing a zero.

The number of datasets does not exceed 100.

Output

For each of the datasets, output one line containing the number of times the four integers 2, 0, 2, and 0 appear consecutively in this order in the list of integers in its second line. Overlapping occurrences are separately counted. “2 0 2 0 2 0 2 0”, for example, is said to have three occurrences, rather than two.

Examples1

  1. Example 1

    Input
    15
2 0 2 0 2 2 0 2 0 2 2 0 2 0 2
20
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
32
1 8 1 9 1 9 2 0 2 0 2 1 2 1 2 2 2 2 2 1 2 1 2 0 2 0 1 9 1 9 1 8
32
2 0 1 8 2 0 1 9 2 0 2 0 2 0 2 1 2 0 2 2 2 0 2 3 2 0 2 1 2 0 2 0
0
    Expected output
    3
0
2
3