#include <fstream>
const int NMAX=2000005;

using namespace std;
ifstream cin("numarare.in");
ofstream cout("numarare.out");

void manacher(int [], int [], int);

int s[NMAX], t[2*NMAX];
int ans[2*NMAX], n;

signed main()
{
    int i;
    long long sum=0;
    cin>>n;
    for(i=0; i<n; i++) cin>>s[i];
    manacher(ans, s, n);
    for(i=0; i<2*n; i++) sum+=(t[i]==-100001)*(ans[i]-1)/2;
    cout<<sum<<'\n';
    return 0;
}

void manacher(int v[], int s[], int n)
{
    int i, lg=0;
    t[lg]=-100001;
    for(i=0; i<n; i++)
    {
        t[++lg]=s[i];
        t[++lg]=-100001;
    }
    int dr=0, st=0, k, sum=-200001;
    for(i=0; i<2*n; i+=2)
    {
        if(i>dr) k=1;
        else k=min(ans[dr+st-i], dr-i+1);
        sum=-200001;
        while(true)
        {
            if(i-k<0 || !t[i+k]) break;
            if(t[i+k]==-100001) k++;
            if(sum==-200001) sum=t[i+k]+t[i-k];
            if(sum==t[i+k]+t[i-k]) k++;
            else break;
        }
        ans[i]=k--;
        if(dr<=i+k)
        {
            dr=i+k;
            st=i-k;
        }
    }
}