#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

ll dp[N][3][3][3];

void __(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]%=3;
        // cout<<a[i]<<" ";
    }
    // cout<<endl;
    ll sum=0;
    for(int i=0;i<=n;i++){
        // dp[i+1][a[i]][a[i]][a[i]]=1;
        
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++) sum+=dp[i][j][k][0];
        }
        // cout<<sum<<endl;
        dp[i][0][0][0]++;
        // if(a[i]==0) dp[i+1][0][0][0]=1;
        // else if(a[i]==1) dp[i+1][1][0][0]=1;
        // else  dp[i+1][0][1][0]=1;

        

        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                for(int u=0;u<3;u++){
                    if(a[i]==0){
                        dp[i+1][j][k][u]+=dp[i][j][k][u];
                    }else if(a[i]==1){
                        dp[i+1][(j+1)%3][k][(u+j+k*2)%3]+=dp[i][j][k][u];
                    }else{
                        dp[i+1][j][(k+1)%3][(u+2*k*2+j*2)%3]+=dp[i][j][k][u];
                    }
                }
            }
        }
    }
    // for(int i=1;i<=n;i++) if(a[i]==0) sum--;

    cout<<sum<<endl;

}


int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}