You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

「壹生贰，贰生叁，叁生万物」。

Description

给定一个长度为 $n$ 的序列 $a_1 \dots a_n$，保证每个 $1 \le a_i \le 9$。

定义 $f(l, r) = \sum_{i = l}^r 10^{r - i}a_i$，即将 $a_l, a_{l + 1} \dots a_r$ 连起来后组成的十进制数。

例如，当 $a = \{1, 1, 4, 5, 1, 4\}$ 时，$f(2, 6) = 14514$，$f(5, 5) = 1$。

求有多少个 $1 \le l \le r \le n$ 的 $f(l, r)$ 是 $3$ 的倍数。

Format

Input

第一行一个整数 $n$，第二行 $n$ 个整数表示 $a_1 \dots a_n$。

Output

一行一个整数表示答案。

Samples

3
3 6 9

6

所有 $1 \le l \le r \le 3$ 的 $f(l, r)$ 均为 $3$ 的倍数。

6
1 1 4 5 1 4

5

$f(1, 3), f(1, 5), f(2, 6), f(3, 4), f(4, 5)$ 均为 $3$ 倍数。

Limitation

对于 $20\%$ 的数据，$n \le 10$；

对于另外 $10\%$ 的数据，保证 $a_i$ 只为 $3, 6, 9$；

对于另外 $20\%$ 的数据，$n \le 2000$；

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le a_i \le 9$。