#include <bits/stdc++.h>
using namespace std;
inline long long in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
inline string get() {
  char ch[2000010];
  scanf("%s", ch);
  return ch;
}
inline void read(long long *a, long long n) {
  for (long long i = 0; i < n; i++) a[i] = in();
}
const long long maxn = 3e5 + 10;
const long long maxm = 1e6 + 10;
const long long maxlg = 21;
const long long base = 29;
const long long mod = 1e9 + 7;
const long long INF = 1e18 + 10;
long long a[maxn], cnt[maxn], odd, l, r, n;
inline bool inside(long long x, long long l, long long r) {
  return x >= l && x <= r;
}
inline bool can(long long l, long long r) {
  for (long long i = 0; i < n; i++) cnt[a[i]] = 0;
  for (long long i = l; i <= r; i++) cnt[a[i]]++;
  bool ret = 1;
  long long even = 0;
  for (long long i = 0; i < n && ret; i++) {
    long long j = n - i - 1;
    if (!inside(i, l, r) && !inside(j, l, r)) {
      if (a[i] != a[j]) ret = 0;
    } else if (!inside(i, l, r) && inside(j, l, r)) {
      if (!cnt[a[i]]) {
        ret = 0;
        break;
      }
      cnt[a[i]]--;
    } else if (inside(i, l, r) && !inside(j, l, r))
      continue;
    else {
      if (i >= j) continue;
      even++;
    }
  }
  for (long long i = 0; i <= n; i++) even -= cnt[i] / 2;
  if (even > 0) return 0;
  return ret;
}
int32_t main() {
  n = in();
  for (long long i = 0; i < n; i++) a[i] = in(), cnt[a[i]]++;
  bool fl = true;
  for (long long i = 0; i < n; i++) fl &= a[i] == a[n - i - 1];
  for (long long i = 0; i < maxn; i++)
    if (cnt[i] % 2) odd++;
  if (odd > 1) return cout << 0 << "\n", 0;
  if (fl) return cout << n * (n + 1) / 2 << "\n", 0;
  l = 0, r = n - 1;
  while (l <= r && a[l] == a[r]) l++, r--;
  long long low = 0, hi = r - l + 1, mid;
  memset(cnt, 0, sizeof cnt);
  while (low + 1 < hi) {
    mid = (low + hi) >> 1;
    bool fl = can(l, l + mid - 1);
    if (fl)
      hi = mid;
    else
      low = mid;
  }
  long long left = hi;
  low = 0, hi = r - l + 1;
  while (low + 1 < hi) {
    mid = (low + hi) >> 1;
    bool fl = can(r - mid + 1, r);
    if (fl)
      hi = mid;
    else
      low = mid;
  }
  long long right = hi;
  long long res =
      (l + 1) * (n - l - left + 1) + (n - r) * max(0ll, (r + 1 - right - l));
  cout << res << "\n";
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
inline long long in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
inline string get() {
  char ch[2000010];
  scanf("%s", ch);
  return ch;
}
inline void read(long long *a, long long n) {
  for (long long i = 0; i < n; i++) a[i] = in();
}
const long long maxn = 3e5 + 10;
const long long maxm = 1e6 + 10;
const long long maxlg = 21;
const long long base = 29;
const long long mod = 1e9 + 7;
const long long INF = 1e18 + 10;
long long a[maxn], cnt[maxn], odd, l, r, n;
inline bool inside(long long x, long long l, long long r) {
  return x >= l && x <= r;
}
inline bool can(long long l, long long r) {
  for (long long i = 0; i < n; i++) cnt[a[i]] = 0;
  for (long long i = l; i <= r; i++) cnt[a[i]]++;
  bool ret = 1;
  long long even = 0;
  for (long long i = 0; i < n && ret; i++) {
    long long j = n - i - 1;
    if (!inside(i, l, r) && !inside(j, l, r)) {
      if (a[i] != a[j]) ret = 0;
    } else if (!inside(i, l, r) && inside(j, l, r)) {
      if (!cnt[a[i]]) {
        ret = 0;
        break;
      }
      cnt[a[i]]--;
    } else if (inside(i, l, r) && !inside(j, l, r))
      continue;
    else {
      if (i >= j) continue;
      even++;
    }
  }
  for (long long i = 0; i <= n; i++) even -= cnt[i] / 2;
  if (even > 0) return 0;
  return ret;
}
int32_t main() {
  n = in();
  for (long long i = 0; i < n; i++) a[i] = in(), cnt[a[i]]++;
  bool fl = true;
  for (long long i = 0; i < n; i++) fl &= a[i] == a[n - i - 1];
  for (long long i = 0; i < maxn; i++)
    if (cnt[i] % 2) odd++;
  if (odd > 1) return cout << 0 << "\n", 0;
  if (fl) return cout << n * (n + 1) / 2 << "\n", 0;
  l = 0, r = n - 1;
  while (l <= r && a[l] == a[r]) l++, r--;
  long long low = 0, hi = r - l + 1, mid;
  memset(cnt, 0, sizeof cnt);
  while (low + 1 < hi) {
    mid = (low + hi) >> 1;
    bool fl = can(l, l + mid - 1);
    if (fl)
      hi = mid;
    else
      low = mid;
  }
  long long left = hi;
  low = 0, hi = r - l + 1;
  while (low + 1 < hi) {
    mid = (low + hi) >> 1;
    bool fl = can(r - mid + 1, r);
    if (fl)
      hi = mid;
    else
      low = mid;
  }
  long long right = hi;
  long long res =
      (l + 1) * (n - l - left + 1) + (n - r) * max(0ll, (r + 1 - right - l));
  cout << res << "\n";
}

```