#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
void amax(X& x, const Y& y) {
  if (x < y) x = y;
}
template <class X, class Y>
void amin(X& x, const Y& y) {
  if (x > y) x = y;
}
const int INF = 1e9 + 10;
const long long INFL = (long long)1e18 + 10;
const int MAX = 1e5 + 10;
int n;
int a[MAX], b[MAX];
int l, r;
int cnt[MAX];
void prepare_seg(int x, int y) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = x; i <= y; i++) cnt[a[i]]++;
  for (int i = l; i <= r; i++) b[i] = a[i];
}
bool check_remain() {
  int sum = 0;
  for (int i = 1; i <= n; i++) sum += cnt[i] % 2;
  return sum <= 1;
}
bool check_palin() {
  for (int i = l, j = r; i <= j; i++, j--)
    if (b[i] != b[j]) return false;
  return true;
}
bool check_left(int x) {
  prepare_seg(l, x);
  int i, j;
  for (i = l, j = r; i <= x && j > x; i++, j--) {
    if (cnt[b[j]] > 0) {
      cnt[b[j]]--;
      b[i] = b[j];
    } else
      return false;
  }
  if (i <= x) return check_remain();
  return check_palin();
}
bool check_right(int x) {
  prepare_seg(x, r);
  int i, j;
  for (i = l, j = r; i < x && j >= x; i++, j--) {
    if (cnt[b[i]] > 0) {
      cnt[b[i]]--;
      b[j] = b[i];
    } else
      return false;
  }
  if (j >= x) return check_remain();
  return check_palin();
}
int find_left(int x, int y) {
  int l = x, r = y, i = (l + r) / 2;
  while (l != i && i != r) {
    if (check_left(i))
      r = i;
    else
      l = i;
    i = (l + r) / 2;
  }
  for (i = l; i <= r; i++)
    if (check_left(i)) return i;
  return -1;
}
int find_right(int x, int y) {
  int l = x, r = y, i = (l + r) / 2;
  while (l != i && i != r) {
    if (check_right(i))
      l = i;
    else
      r = i;
    i = (l + r) / 2;
  }
  for (i = r; i >= l; i--)
    if (check_right(i)) return i;
  return -1;
}
void process() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  l = 1;
  r = n;
  while (l <= r) {
    if (a[l] == a[r])
      l++, r--;
    else
      break;
  }
  if (l > r) {
    cout << (long long)n * (n + 1) / 2;
    return;
  }
  if (!check_left(r)) {
    cout << 0;
    return;
  }
  long long res = (long long)l * (n - r + 1);
  int vl = find_left(l, r);
  int vr = find_right(l, r);
  if (vl != -1) {
    res += (long long)(r - vl) * l;
  }
  if (vr != -1) {
    res += (long long)(vr - l) * (n - r + 1);
  }
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  process();
}

### 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;
template <class X, class Y>
void amax(X& x, const Y& y) {
  if (x < y) x = y;
}
template <class X, class Y>
void amin(X& x, const Y& y) {
  if (x > y) x = y;
}
const int INF = 1e9 + 10;
const long long INFL = (long long)1e18 + 10;
const int MAX = 1e5 + 10;
int n;
int a[MAX], b[MAX];
int l, r;
int cnt[MAX];
void prepare_seg(int x, int y) {
  memset(cnt, 0, sizeof(cnt));
  for (int i = x; i <= y; i++) cnt[a[i]]++;
  for (int i = l; i <= r; i++) b[i] = a[i];
}
bool check_remain() {
  int sum = 0;
  for (int i = 1; i <= n; i++) sum += cnt[i] % 2;
  return sum <= 1;
}
bool check_palin() {
  for (int i = l, j = r; i <= j; i++, j--)
    if (b[i] != b[j]) return false;
  return true;
}
bool check_left(int x) {
  prepare_seg(l, x);
  int i, j;
  for (i = l, j = r; i <= x && j > x; i++, j--) {
    if (cnt[b[j]] > 0) {
      cnt[b[j]]--;
      b[i] = b[j];
    } else
      return false;
  }
  if (i <= x) return check_remain();
  return check_palin();
}
bool check_right(int x) {
  prepare_seg(x, r);
  int i, j;
  for (i = l, j = r; i < x && j >= x; i++, j--) {
    if (cnt[b[i]] > 0) {
      cnt[b[i]]--;
      b[j] = b[i];
    } else
      return false;
  }
  if (j >= x) return check_remain();
  return check_palin();
}
int find_left(int x, int y) {
  int l = x, r = y, i = (l + r) / 2;
  while (l != i && i != r) {
    if (check_left(i))
      r = i;
    else
      l = i;
    i = (l + r) / 2;
  }
  for (i = l; i <= r; i++)
    if (check_left(i)) return i;
  return -1;
}
int find_right(int x, int y) {
  int l = x, r = y, i = (l + r) / 2;
  while (l != i && i != r) {
    if (check_right(i))
      l = i;
    else
      r = i;
    i = (l + r) / 2;
  }
  for (i = r; i >= l; i--)
    if (check_right(i)) return i;
  return -1;
}
void process() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  l = 1;
  r = n;
  while (l <= r) {
    if (a[l] == a[r])
      l++, r--;
    else
      break;
  }
  if (l > r) {
    cout << (long long)n * (n + 1) / 2;
    return;
  }
  if (!check_left(r)) {
    cout << 0;
    return;
  }
  long long res = (long long)l * (n - r + 1);
  int vl = find_left(l, r);
  int vr = find_right(l, r);
  if (vl != -1) {
    res += (long long)(r - vl) * l;
  }
  if (vr != -1) {
    res += (long long)(vr - l) * (n - r + 1);
  }
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  process();
}

```