정수 배열 $[b_1, b_2, \dots, b_m]$에 대하여, 그 가중치(weight)를 모든 원소 쌍의 곱의 합, 즉 $1 \le i < j \le m$인 모든 $i, j$에 대하여 $b_i b_j$의 합으로 정의하자.

$n$개의 정수로 이루어진 배열 $[a_1, a_2, \dots, a_n]$이 주어질 때, 부분 배열 $[a_l, a_{l+1}, \dots, a_r]$의 가중치가 3으로 나누어떨어지는 정수 쌍 $(l, r)$ ($1 \le l \le r \le n$)의 개수를 구하시오.

입력

첫 번째 줄에는 배열의 길이인 정수 $n$ ($1 \le n \le 5 \cdot 10^5$)이 주어진다.

두 번째 줄에는 배열의 원소인 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)이 주어진다.

출력

부분 배열의 가중치가 3으로 나누어떨어지는 정수 쌍 $(l, r)$ ($1 \le l \le r \le n$)의 개수를 하나의 정수로 출력하시오.

예제

입력 1

3
5 23 2021

출력 1

4

입력 2

5
0 0 1 3 3

출력 2

15

입력 3

10
0 1 2 3 4 5 6 7 8 9

출력 3

20

참고

첫 번째 예제에서, 가중치가 3으로 나누어떨어지는 부분 배열은 정확히 4개이다.

• $\text{weight}([5]) = \text{weight}([23]) = \text{weight}([2021]) = 0$
• $\text{weight}([5, 23, 2021]) = 56703 = 3 \cdot 41 \cdot 461$