Count Positives at Multiples of Three

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Count 1-based positions i divisible by 3 whose value ai is strictly positive.

Input

0<=n<=100000, followed by n integers in [-1000000,1000000].

Output

The number of positions satisfying both conditions.

Subtasks

• Subtask 1 (20%): n<=6, |ai|<=10.
• Subtask 2 (30%): n<=100, |ai|<=1000.
• Subtask 3 (50%): n<=100000, |ai|<=1000000.

Examples

Example 1

Input

6
1 -2 3 4 5 6

Output

2

Explanation

Only positions 3 and 6 meet both conditions.

Example 2

Input

3
1 2 0

Output

0

Explanation

The third value is zero, not positive.