#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
const int maxn = 100000 + 16;
int n;
int a[maxn];
int c_odd;
int c[maxn];
void init1() {
  c_odd = 0;
  memset(c, 0, sizeof(c));
}
bool is_ok1() {
  if (n & 1) return c_odd <= 1;
  return c_odd <= 0;
}
void update(int p, int d) {
  c_odd -= (c[p] & 1);
  c[p] += d;
  c_odd += (c[p] & 1);
}
long long count1(int s, int t) {
  if (s > t) return 0;
  return (long long)(s + 1) * (long long)(n - t);
}
long long count1(int s1, int t1, int s2, int t2) {
  return count1(s1, t1) + count1(s2, t2) - count1(min(s1, s2), max(t1, t2));
}
long long solve() {
  init1();
  for (int i = 0; i < n; i++) update(a[i], 1);
  if (!is_ok1()) return 0;
  int L = 0, R = n - 1;
  while (L < R) {
    if (a[L] != a[R]) break;
    update(a[L], -1);
    update(a[R], -1);
    L++, R--;
  }
  if (L >= R) return (long long)n * (long long)(n + 1) / 2;
  init1();
  for (int i = L; i <= R; i++) update(a[i], 1);
  int p = R;
  for (; p > (n + 1) / 2; p--) {
    update(a[p], -1);
    update(a[p], -1);
    if (c[a[p]] < 0) break;
    if (!is_ok1()) break;
  }
  init1();
  for (int i = L; i <= R; i++) update(a[i], 1);
  int q = L;
  for (; q < n / 2 - 1; q++) {
    update(a[q], -1);
    update(a[q], -1);
    if (c[a[q]] < 0) break;
    if (!is_ok1()) break;
  }
  long long ret1 = count1(L, p, q, R);
  p = (n - 1) / 2;
  q = n / 2;
  for (; a[p] == a[q]; p--, q++)
    ;
  init1();
  for (int i = L; i <= p; i++) c[a[i]]++;
  for (int i = q; i <= R; i++) c[a[i]]--;
  long long ret2 = 0;
  bool ok = true;
  for (int i = 0; i < maxn; i++)
    if (c[i]) ok = false;
  if (ok) ret2 = (long long)(L + 1) * (n / 2 - p);
  long long ret3 = 0;
  if (n % 2 == 1) {
    init1();
    for (int i = L; i < n / 2; i++) c[a[i]]++;
    for (int i = n / 2 + 1; i <= R; i++) c[a[i]]--;
    c[a[n / 2]]++;
    int sc = 0;
    for (int i = 0; i < maxn; i++) sc += abs(c[i]);
    if (sc <= 1) ret3 += (long long)(L + 1);
    c[a[n / 2]] -= 2;
    sc = 0;
    for (int i = 0; i < maxn; i++) sc += abs(c[i]);
    if (sc <= 1) ret3 += (long long)(L + 1);
  }
  return ret1 + ret2 * 2 + ret3;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long ret = solve();
  cout << ret << endl;
  return 0;
}

### Prompt

Please formulate 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;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
const int maxn = 100000 + 16;
int n;
int a[maxn];
int c_odd;
int c[maxn];
void init1() {
  c_odd = 0;
  memset(c, 0, sizeof(c));
}
bool is_ok1() {
  if (n & 1) return c_odd <= 1;
  return c_odd <= 0;
}
void update(int p, int d) {
  c_odd -= (c[p] & 1);
  c[p] += d;
  c_odd += (c[p] & 1);
}
long long count1(int s, int t) {
  if (s > t) return 0;
  return (long long)(s + 1) * (long long)(n - t);
}
long long count1(int s1, int t1, int s2, int t2) {
  return count1(s1, t1) + count1(s2, t2) - count1(min(s1, s2), max(t1, t2));
}
long long solve() {
  init1();
  for (int i = 0; i < n; i++) update(a[i], 1);
  if (!is_ok1()) return 0;
  int L = 0, R = n - 1;
  while (L < R) {
    if (a[L] != a[R]) break;
    update(a[L], -1);
    update(a[R], -1);
    L++, R--;
  }
  if (L >= R) return (long long)n * (long long)(n + 1) / 2;
  init1();
  for (int i = L; i <= R; i++) update(a[i], 1);
  int p = R;
  for (; p > (n + 1) / 2; p--) {
    update(a[p], -1);
    update(a[p], -1);
    if (c[a[p]] < 0) break;
    if (!is_ok1()) break;
  }
  init1();
  for (int i = L; i <= R; i++) update(a[i], 1);
  int q = L;
  for (; q < n / 2 - 1; q++) {
    update(a[q], -1);
    update(a[q], -1);
    if (c[a[q]] < 0) break;
    if (!is_ok1()) break;
  }
  long long ret1 = count1(L, p, q, R);
  p = (n - 1) / 2;
  q = n / 2;
  for (; a[p] == a[q]; p--, q++)
    ;
  init1();
  for (int i = L; i <= p; i++) c[a[i]]++;
  for (int i = q; i <= R; i++) c[a[i]]--;
  long long ret2 = 0;
  bool ok = true;
  for (int i = 0; i < maxn; i++)
    if (c[i]) ok = false;
  if (ok) ret2 = (long long)(L + 1) * (n / 2 - p);
  long long ret3 = 0;
  if (n % 2 == 1) {
    init1();
    for (int i = L; i < n / 2; i++) c[a[i]]++;
    for (int i = n / 2 + 1; i <= R; i++) c[a[i]]--;
    c[a[n / 2]]++;
    int sc = 0;
    for (int i = 0; i < maxn; i++) sc += abs(c[i]);
    if (sc <= 1) ret3 += (long long)(L + 1);
    c[a[n / 2]] -= 2;
    sc = 0;
    for (int i = 0; i < maxn; i++) sc += abs(c[i]);
    if (sc <= 1) ret3 += (long long)(L + 1);
  }
  return ret1 + ret2 * 2 + ret3;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long ret = solve();
  cout << ret << endl;
  return 0;
}

```