Misha has an array of n integers indexed by integers from 1 to n. Let's define palindrome degree of array a as the number of such index pairs (l, r)(1 ≤ l ≤ r ≤ n), that the elements from the l-th to the r-th one inclusive can be rearranged in such a way that the whole array will be a palindrome. In other words, pair (l, r) should meet the condition that after some rearranging of numbers on positions from l to r, inclusive (it is allowed not to rearrange the numbers at all), for any 1 ≤ i ≤ n following condition holds: a[i] = a[n - i + 1]. 

Your task is to find the palindrome degree of Misha's array.

Input

The first line contains integer n (1 ≤ n ≤ 105).

The second line contains n positive integers a[i] (1 ≤ a[i] ≤ n), separated by spaces — the elements of Misha's array.

Output

In a single line print the answer to the problem.

Examples

Input

3
2 2 2


Output

6


Input

6
3 6 5 3 3 5


Output

0


Input

5
5 5 2 5 2


Output

4

Note

In the first sample test any possible pair (l, r) meets the condition.

In the third sample test following pairs (1, 3), (1, 4), (1, 5), (2, 5) meet the condition.
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
const int N = (int)(3e5 + 20);
const int L = 360;
const long long int M = (int)(1e9 + 7);
const double E = 1e-7;
bool isPal = true;
bool canBePalindrome = false;
int a[N], cnt[N];
int cnts[N], cntL[N], cntR[N];
struct solution {
  long long int left, right, total;
  solution(long long int l, long long int r, long long int t)
      : left(l), right(r), total(t) {}
};
long long int solveR(long long int l, long long int r) {
  int dif = 0;
  int bl = l, br = r;
  bool canPal = true;
  int cntOdd = 0;
  for (int i = l; i <= r; ++i) {
    cnts[a[i]]++;
    cntOdd += (cnts[a[i]] & 1) ? 1 : -1;
  }
  int lastChanged = br;
  while (bl < br) {
    int o = r - (bl - l);
    if (o < bl) break;
    if (cnts[a[bl]] < 2 - (o == bl)) {
      lastChanged = bl;
      break;
    }
    if (a[o] != a[bl]) {
      lastChanged = o;
    }
    cnts[a[bl]] -= 2;
    bl++;
  }
  return lastChanged - l + 1;
}
long long int solveL(long long int l, long long int r) {
  int dif = 0;
  int bl = l, br = r;
  bool canPal = true;
  int cntOdd = 0;
  for (int i = l; i <= r; ++i) {
    cnts[a[i]]++;
    cntOdd += (cnts[a[i]] & 1) ? 1 : -1;
  }
  int lastChanged = br;
  while (bl < br) {
    int o = l + (r - br);
    if (o > br) break;
    if (cnts[a[br]] < 2 - (o == l)) {
      lastChanged = br;
      break;
    }
    if (a[o] != a[br]) {
      lastChanged = o;
    }
    cnts[a[bl]] -= 2;
    br--;
  }
  return r - lastChanged + 1;
}
solution solve(long long int l, long long int r) {
  if (l == r) return solution(1, 1, 1);
  if (a[l] == a[r]) {
    solution sol = solve(l + 1, r - 1);
    sol.left *= 2;
    sol.right *= 2;
    sol.total = sol.left + sol.right;
    return sol;
  }
  long long int rans = solveR(l, r);
  reverse(a + l, a + r + 1);
  memset(cnts, 0, N * sizeof(int));
  long long int lans = solveR(l, r);
  return solution(lans, rans, lans + rans - 1);
}
int main() {
  ios_base::sync_with_stdio(0);
  long long int n;
  cin >> n;
  int cntOdd = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    cnt[a[i]]++;
    isPal &= (i < (n / 2)) || a[i] == a[n - i - 1];
    cntOdd += (cnt[a[i]] & 1) ? 1 : -1;
  }
  canBePalindrome = cntOdd <= 1;
  if (isPal)
    cout << (n * (n + 1) / 2);
  else if (!canBePalindrome)
    cout << 0;
  else
    cout << solve(0, n - 1).total;
}
