#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1.0);
const long long LINF = (long long)1e18 + 5;
const int INF = (int)1e9 + 5;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
long long round(T x) {
  return x < 0 ? x - 0.5 : x + 0.5;
}
template <class T>
bool chmin(T& x, const T& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& x, const T& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const pair<P, Q>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool was = false;
  os << "{";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  bool was = false;
  os << "{";
  for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  bool was = false;
  os << "{";
  for (typename multiset<T>::const_iterator it = v.begin(); it != v.end();
       it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const map<P, Q>& v) {
  bool was = false;
  os << "{";
  for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
string nextToken() {
  static char str[(int)1e6 + 5];
  scanf("%s", str);
  return str;
}
template <class T>
T nextInt() {
  long long x = 0;
  bool p = false;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return (p ? -x : x);
}
const int N = 100500;
int ft[N];
void addFT(int r, int val) {
  while (r < N) {
    ft[r] += val;
    r |= r + 1;
  }
}
int sumFT(int r) {
  int sum = 0;
  while (r >= 0) {
    sum += ft[r];
    r = (r & (r + 1)) - 1;
  }
  return sum;
}
int sumFT(int l, int r) { return sumFT(r) - sumFT(l - 1); }
int n, a[N];
map<int, int> mapp;
bool flag;
bool good[N], good2[N];
bool check(int l, int r) {
  if (l > r) return false;
  if (r <= n / 2) {
    return flag && sumFT(1, n / 2) - sumFT(l, r) == 0;
  }
  if (l > (n + 1) / 2) {
    return flag && sumFT((n + 1) / 2 + 1, n) - sumFT(l, r) == 0;
  }
  int invL = n - r + 1;
  int invR = n - l + 1;
  int nL = min(l, invL);
  int nR = max(r, invR);
  return good[l - 1] && good2[r] && sumFT(1, n) - sumFT(nL, nR) == 0;
}
void solve(int tc) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    mapp[a[i]]++;
  }
  int cntOdd = 0;
  for (auto p : mapp) {
    if (p.second % 2 == 1) cntOdd++;
  }
  if (cntOdd > 1) {
    puts("0");
    return;
  }
  multiset<int> half1, half2;
  for (int i = 1; i <= n / 2; i++) {
    half1.insert(a[i]);
  }
  for (int i = (n + 1) / 2 + 1; i <= n; i++) {
    half2.insert(a[i]);
  }
  flag = half1 == half2;
  for (int i = 1; i <= n / 2; i++) {
    if (a[i] != a[n - i + 1]) {
      addFT(i, 1);
      addFT(n - i + 1, 1);
    }
  }
  good[0] = true;
  static int z[N] = {};
  int cntBad = 0;
  for (int i = 1; i <= n; i++) {
    z[a[i]]++;
  }
  for (int r = 1; r <= n; r++) {
    int x = a[r];
    z[x] -= 2;
    if (z[x] + 2 >= 0 && z[x] < 0) cntBad++;
    good[r] = cntBad == 0;
  }
  memset(z, 0, sizeof(z));
  good2[n] = true;
  cntBad = 0;
  for (int i = 1; i <= n; i++) {
    z[a[i]]++;
  }
  for (int r = n; r >= 1; r--) {
    int x = a[r];
    z[x] -= 2;
    if (z[x] + 2 >= 0 && z[x] < 0) cntBad++;
    good2[r - 1] = cntBad == 0;
  }
  long long res = 0;
  for (int l = 1; l <= n; l++) {
    int lf = 0, rg = n + 1;
    while (rg - lf > 1) {
      int mid = (lf + rg) >> 1;
      if (check(l, mid))
        rg = mid;
      else
        lf = mid;
    }
    res += n - rg + 1;
  }
  cout << res << endl;
}
int main(int argc, char* argv[]) {
  srand(time(0));
  int t = 1;
  for (int tc = 1; tc <= t; tc++) {
    solve(tc);
  }
}

### Prompt

Your task is to create 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 long double PI = acos(-1.0);
const long long LINF = (long long)1e18 + 5;
const int INF = (int)1e9 + 5;
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
long long round(T x) {
  return x < 0 ? x - 0.5 : x + 0.5;
}
template <class T>
bool chmin(T& x, const T& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& x, const T& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const pair<P, Q>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  bool was = false;
  os << "{";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& v) {
  bool was = false;
  os << "{";
  for (typename set<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  bool was = false;
  os << "{";
  for (typename multiset<T>::const_iterator it = v.begin(); it != v.end();
       it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
template <class P, class Q>
ostream& operator<<(ostream& os, const map<P, Q>& v) {
  bool was = false;
  os << "{";
  for (typename map<P, Q>::const_iterator it = v.begin(); it != v.end(); it++) {
    if (was) {
      os << ", ";
    } else {
      was = true;
    }
    os << *it;
  }
  os << "}";
  return os;
}
string nextToken() {
  static char str[(int)1e6 + 5];
  scanf("%s", str);
  return str;
}
template <class T>
T nextInt() {
  long long x = 0;
  bool p = false;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return (p ? -x : x);
}
const int N = 100500;
int ft[N];
void addFT(int r, int val) {
  while (r < N) {
    ft[r] += val;
    r |= r + 1;
  }
}
int sumFT(int r) {
  int sum = 0;
  while (r >= 0) {
    sum += ft[r];
    r = (r & (r + 1)) - 1;
  }
  return sum;
}
int sumFT(int l, int r) { return sumFT(r) - sumFT(l - 1); }
int n, a[N];
map<int, int> mapp;
bool flag;
bool good[N], good2[N];
bool check(int l, int r) {
  if (l > r) return false;
  if (r <= n / 2) {
    return flag && sumFT(1, n / 2) - sumFT(l, r) == 0;
  }
  if (l > (n + 1) / 2) {
    return flag && sumFT((n + 1) / 2 + 1, n) - sumFT(l, r) == 0;
  }
  int invL = n - r + 1;
  int invR = n - l + 1;
  int nL = min(l, invL);
  int nR = max(r, invR);
  return good[l - 1] && good2[r] && sumFT(1, n) - sumFT(nL, nR) == 0;
}
void solve(int tc) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    mapp[a[i]]++;
  }
  int cntOdd = 0;
  for (auto p : mapp) {
    if (p.second % 2 == 1) cntOdd++;
  }
  if (cntOdd > 1) {
    puts("0");
    return;
  }
  multiset<int> half1, half2;
  for (int i = 1; i <= n / 2; i++) {
    half1.insert(a[i]);
  }
  for (int i = (n + 1) / 2 + 1; i <= n; i++) {
    half2.insert(a[i]);
  }
  flag = half1 == half2;
  for (int i = 1; i <= n / 2; i++) {
    if (a[i] != a[n - i + 1]) {
      addFT(i, 1);
      addFT(n - i + 1, 1);
    }
  }
  good[0] = true;
  static int z[N] = {};
  int cntBad = 0;
  for (int i = 1; i <= n; i++) {
    z[a[i]]++;
  }
  for (int r = 1; r <= n; r++) {
    int x = a[r];
    z[x] -= 2;
    if (z[x] + 2 >= 0 && z[x] < 0) cntBad++;
    good[r] = cntBad == 0;
  }
  memset(z, 0, sizeof(z));
  good2[n] = true;
  cntBad = 0;
  for (int i = 1; i <= n; i++) {
    z[a[i]]++;
  }
  for (int r = n; r >= 1; r--) {
    int x = a[r];
    z[x] -= 2;
    if (z[x] + 2 >= 0 && z[x] < 0) cntBad++;
    good2[r - 1] = cntBad == 0;
  }
  long long res = 0;
  for (int l = 1; l <= n; l++) {
    int lf = 0, rg = n + 1;
    while (rg - lf > 1) {
      int mid = (lf + rg) >> 1;
      if (check(l, mid))
        rg = mid;
      else
        lf = mid;
    }
    res += n - rg + 1;
  }
  cout << res << endl;
}
int main(int argc, char* argv[]) {
  srand(time(0));
  int t = 1;
  for (int tc = 1; tc <= t; tc++) {
    solve(tc);
  }
}

```