For an array [b1,b2,...,bm] of integers, let's define its weight as the sum of pairwise products of its elements, namely as the sum of bi⋅bj over 1≤i<j≤m.
You are given an array of n integers [a1,a2,...,an], and are asked to find the number of pairs of integers (l,r) with 1≤l≤r≤n, for which the weight of the subarray [al,al+1,...,ar] is divisible by 3.
The first line contains a single integer n (1≤n≤5⋅105) — the length of the array.
The second line contains n integers a1,a2,...,an (0≤ai≤109) — the elements of the array.
Output a single integer — the number of pairs of integers (l,r) with 1≤l≤r≤n, for which the weight of the corresponding subarray is divisible by 3.