#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 3;
const ull BASE = 179424673;
const ull MOD = 1e9 + 7;

int n, a[N];
ull h[N], b[N], rev_h[N], inv_b[N];
int mx[2][N];

ull fast_pow(ull base, ull exp){
    if(!exp) return 1;
    if(exp & 1) return fast_pow(base, exp - 1) * base;
    ull t = fast_pow(base, exp >> 1);
    return t * t;
}

ull get_hash(int l, int r){
    return h[r] - h[l - 1] * b[r - l + 1];
}

ull get_rev_hash(int l, int r){
    return rev_h[l] - rev_h[r + 1] * b[r - l + 1];
}

ll solve(int l, int r){
    //cout << "solve " << l << " " << r << endl; 
    pair<int, int> best{-1, -1};
    for(int i = l; i <= r; ++i)
        check_max(best, {min(mx[0][i], min(i - l + 1, r - i + 1)) * 2 - 1, i});
    for(int i = l; i <= r - 1; ++i)
        check_max(best, {min(mx[1][i], min(i - l + 1, r - i)) * 2, i});

    if(best.second == -1) return 0ll;

    ll ans = (ll)best.first * (ll)best.first;
    bool odd = (best.first & 1);
    best.first += 1;
    best.first /= 2;

    if(odd){
        ans += solve(l, best.second - best.first);
        ans += solve(best.second + best.first, r);
    }
    else{
        ans += solve(l, best.second - best.first);
        ans += solve(best.second + best.first + 1, r);
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("split.in", "r", stdin);
    freopen("split.out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    b[0] = 1;
    for(int i = 1; i <= n; ++i){
        b[i] = b[i - 1] * BASE;
    }

    h[0] = 0;
    for(int i = 1; i <= n; ++i){
        h[i] = (h[i - 1] * BASE + a[i]);
    }

    rev_h[n + 1] = 0;
    for(int i = n; i >= 1; --i)
        rev_h[i] = (rev_h[i + 1] * BASE + a[i]);

    inv_b[0] = 1;
    inv_b[1] = fast_pow(BASE, MOD - 2);
    for(int i = 2; i <= n; ++i)
        inv_b[i] = (inv_b[i - 1] * inv_b[1]);

    //cout << get_hash(1, 3) << "\n";
    //cout << get_rev_hash(1, 3) << "\n";

    for(int i = 1; i <= n; ++i){
        int l = 1, r = min(i, n - i + 1);
        while(l != r){
            int mid = (l + r + 1) >> 1;
            if(get_hash(i - mid + 1, i) == get_rev_hash(i, i + mid - 1))
                l = mid;
            else
                r = mid - 1;
        }
        mx[0][i] = l;
    }

    //cout << mx[0][2] << endl;

    for(int i = 1; i <= n - 1; ++i){
        int l = 0, r = min(i, n - i);
        while(l != r){
            int mid = (l + r + 1) >> 1;
            if(get_hash(i - mid + 1, i) == get_rev_hash(i + 1, i + mid))
                l = mid;
            else
                r = mid - 1;
        }
        mx[1][i] = l;
    }

    cout << solve(1, n) << "\n";
}