#include <bits/stdc++.h>
using namespace std;
const int N = 100500;
const int P = 100501;
const int C = 2;
const int MOD[] = {(int)1e9 + 7, (int)1e9 + 9};
int add(int i, int a, int b) {
  int mod = MOD[i];
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int sub(int i, int a, int b) {
  int mod = MOD[i];
  a -= b;
  if (a < 0) a += mod;
  return a;
}
int mul(int i, int a, int b) {
  int mod = MOD[i];
  long long c = (long long)a * b;
  return (int)(c % mod);
}
int pow_p[C][N];
struct Hash {
  int a[C];
  Hash() : a() {}
  int& operator[](int p) { return a[p]; }
  int operator[](int p) const { return a[p]; }
  Hash(int c, int p) {
    for (int i = 0; i < C; i++) a[i] = mul(i, c, pow_p[i][p]);
  }
  Hash operator+(const Hash& b) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = add(i, a[i], b[i]);
    return res;
  }
  Hash operator-(const Hash& b) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = sub(i, a[i], b[i]);
    return res;
  }
  Hash up(int p) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = mul(i, a[i], pow_p[i][p]);
    return res;
  }
  bool operator==(const Hash& b) const {
    for (int i = 0; i < C; i++)
      if (a[i] != b[i]) return false;
    return true;
  }
  bool operator!=(const Hash& b) const { return !(*this == b); }
};
struct HashedString {
  int n;
  int s[N];
  Hash h[N];
  HashedString() : n(), s() {}
  int operator[](int p) const { return s[p]; }
  void build() {
    for (int i = 0; i < n; i++) {
      h[i] = Hash(s[i], i);
      if (i > 0) h[i] = h[i] + h[i - 1];
    }
  }
  Hash get_hash(int l, int r) {
    if (l > r) return Hash();
    Hash x = h[r];
    if (l > 0) x = x - h[l - 1];
    return x.up(n - 1 - l);
  }
};
int n;
int lmid, rmid;
HashedString a, b;
int cnt[N];
int neg_cnt, pos_odd_cnt;
void recalc(int c, int d) {
  if (cnt[c] < 0) neg_cnt += d;
  if (cnt[c] >= 0 && cnt[c] % 2 == 1) pos_odd_cnt += d;
}
void put(int c, int d) {
  recalc(c, -1);
  cnt[c] += d;
  recalc(c, 1);
}
void update(int p, int d) {
  put(a[p], d);
  put(a[n - 1 - p], -d);
}
void update_left(int l, int r) {
  update(l, -1);
  if (l <= lmid && rmid <= r) {
    int p = n - 1 - l;
    if (l <= p && p <= r) {
      put(a[l], -1);
      if (l != p) put(a[p], -1);
    }
  }
}
void update_right(int l, int r) {
  update(r, 1);
  if (l <= lmid && rmid <= r) {
    int p = n - 1 - r;
    if (l <= p && p <= r) {
      put(a[p], 1);
      if (p != r) put(a[r], 1);
    }
  }
}
bool good(int l, int r) {
  if (neg_cnt > 0) return false;
  if (pos_odd_cnt > 1) return false;
  int d = min(l, n - 1 - r) - 1;
  if (a.get_hash(0, d) != b.get_hash(0, d)) return false;
  d = -1;
  if (r <= lmid)
    d = lmid - r - 1;
  else if (rmid <= l)
    d = l - rmid - 1;
  if (a.get_hash(lmid - d, lmid) != b.get_hash(lmid - d, lmid)) return false;
  return true;
}
void solve() {
  for (int i = 0; i < C; i++) {
    pow_p[i][0] = 1;
    for (int j = 1; j < N; j++) pow_p[i][j] = mul(i, pow_p[i][j - 1], P);
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a.s[i]);
  copy(a.s, a.s + n, b.s);
  reverse(b.s, b.s + n);
  a.n = b.n = n;
  lmid = rmid = n / 2;
  if (n % 2 == 0) lmid--;
  a.build();
  b.build();
  int l = 0;
  long long ans = 0;
  for (int r = 0; r < n; r++) {
    update_right(l, r);
    while (l <= r && good(l, r)) {
      update_left(l, r);
      l++;
    }
    ans += l;
  }
  printf("%lld\n", ans);
}
int main() {
  solve();
  0;
  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 int N = 100500;
const int P = 100501;
const int C = 2;
const int MOD[] = {(int)1e9 + 7, (int)1e9 + 9};
int add(int i, int a, int b) {
  int mod = MOD[i];
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
int sub(int i, int a, int b) {
  int mod = MOD[i];
  a -= b;
  if (a < 0) a += mod;
  return a;
}
int mul(int i, int a, int b) {
  int mod = MOD[i];
  long long c = (long long)a * b;
  return (int)(c % mod);
}
int pow_p[C][N];
struct Hash {
  int a[C];
  Hash() : a() {}
  int& operator[](int p) { return a[p]; }
  int operator[](int p) const { return a[p]; }
  Hash(int c, int p) {
    for (int i = 0; i < C; i++) a[i] = mul(i, c, pow_p[i][p]);
  }
  Hash operator+(const Hash& b) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = add(i, a[i], b[i]);
    return res;
  }
  Hash operator-(const Hash& b) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = sub(i, a[i], b[i]);
    return res;
  }
  Hash up(int p) {
    Hash res;
    for (int i = 0; i < C; i++) res[i] = mul(i, a[i], pow_p[i][p]);
    return res;
  }
  bool operator==(const Hash& b) const {
    for (int i = 0; i < C; i++)
      if (a[i] != b[i]) return false;
    return true;
  }
  bool operator!=(const Hash& b) const { return !(*this == b); }
};
struct HashedString {
  int n;
  int s[N];
  Hash h[N];
  HashedString() : n(), s() {}
  int operator[](int p) const { return s[p]; }
  void build() {
    for (int i = 0; i < n; i++) {
      h[i] = Hash(s[i], i);
      if (i > 0) h[i] = h[i] + h[i - 1];
    }
  }
  Hash get_hash(int l, int r) {
    if (l > r) return Hash();
    Hash x = h[r];
    if (l > 0) x = x - h[l - 1];
    return x.up(n - 1 - l);
  }
};
int n;
int lmid, rmid;
HashedString a, b;
int cnt[N];
int neg_cnt, pos_odd_cnt;
void recalc(int c, int d) {
  if (cnt[c] < 0) neg_cnt += d;
  if (cnt[c] >= 0 && cnt[c] % 2 == 1) pos_odd_cnt += d;
}
void put(int c, int d) {
  recalc(c, -1);
  cnt[c] += d;
  recalc(c, 1);
}
void update(int p, int d) {
  put(a[p], d);
  put(a[n - 1 - p], -d);
}
void update_left(int l, int r) {
  update(l, -1);
  if (l <= lmid && rmid <= r) {
    int p = n - 1 - l;
    if (l <= p && p <= r) {
      put(a[l], -1);
      if (l != p) put(a[p], -1);
    }
  }
}
void update_right(int l, int r) {
  update(r, 1);
  if (l <= lmid && rmid <= r) {
    int p = n - 1 - r;
    if (l <= p && p <= r) {
      put(a[p], 1);
      if (p != r) put(a[r], 1);
    }
  }
}
bool good(int l, int r) {
  if (neg_cnt > 0) return false;
  if (pos_odd_cnt > 1) return false;
  int d = min(l, n - 1 - r) - 1;
  if (a.get_hash(0, d) != b.get_hash(0, d)) return false;
  d = -1;
  if (r <= lmid)
    d = lmid - r - 1;
  else if (rmid <= l)
    d = l - rmid - 1;
  if (a.get_hash(lmid - d, lmid) != b.get_hash(lmid - d, lmid)) return false;
  return true;
}
void solve() {
  for (int i = 0; i < C; i++) {
    pow_p[i][0] = 1;
    for (int j = 1; j < N; j++) pow_p[i][j] = mul(i, pow_p[i][j - 1], P);
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a.s[i]);
  copy(a.s, a.s + n, b.s);
  reverse(b.s, b.s + n);
  a.n = b.n = n;
  lmid = rmid = n / 2;
  if (n % 2 == 0) lmid--;
  a.build();
  b.build();
  int l = 0;
  long long ans = 0;
  for (int r = 0; r < n; r++) {
    update_right(l, r);
    while (l <= r && good(l, r)) {
      update_left(l, r);
      l++;
    }
    ans += l;
  }
  printf("%lld\n", ans);
}
int main() {
  solve();
  0;
  return 0;
}

```