import java.util.Scanner;

public class DivisibleByThree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        // Initialize prefix sums and dp array
        int prefixSum = 0;
        int prefixSquareSum = 0;
        int[][] dp = new int[3][3];
        dp[0][0] = 1;  // Base case: empty subarray

        long count = 0;

        for (int num : array) {
            // Update prefix sums
            prefixSum = (prefixSum + num) % 3;
            if (prefixSum < 0) {
                prefixSum += 3;
            }
            prefixSquareSum = (prefixSquareSum + num * num) % 3;
            if (prefixSquareSum < 0) {
                prefixSquareSum += 3;
            }

            // Check all (x, y) pairs in dp array
            for (int x = 0; x < 3; x++) {
                for (int y = 0; y < 3; y++) {
                    if ((prefixSum - x + 3) % 3 * (prefixSum - x + 3) % 3 == (prefixSquareSum - y + 3) % 3) {
                        count += dp[x][y];
                    }
                }
            }

            // Update dp array
            dp[prefixSum][prefixSquareSum]++;
        }

        System.out.println(count);
    }
}