#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int inf = 1000000007;
const long long linf = 1000000000000000000LL;
const unsigned long long ulinf = (1ULL << 63) - 10ULL;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T a) {
  return a >= 0 ? a : -a;
}
template <class T>
int sign(T a) {
  return a > eps ? 1 : a < -eps ? -1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  T ret = a % b;
  if (ret < 0) ret += b;
  return ret;
}
template <class T>
T lowbit(T x) {
  return x & -x;
}
long long addmod(long long a, long long b, long long c) {
  return ((a + b) % c + c) % c;
}
long long mulmod(long long a, long long b, long long c) {
  if (b == 0LL) return 0LL;
  long long ret = mulmod(a, b >> 1, c);
  ret = (ret + ret) % c;
  if (b & 1LL) ret = (ret + a) % c;
  return ret;
}
long long powmod(long long a, long long b, long long c) {
  if (b == 0LL) return 1LL;
  long long ret = powmod(a, b >> 1, c);
  ret = ret * ret % c;
  if (b & 1LL) ret = ret * a % c;
  return ret;
}
long long modinv(long long a, long long b) { return powmod(a, b - 2LL, b); }
template <class T>
void maxe(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void mine(T &a, T b) {
  if (a > b) a = b;
}
int iszero(double a) { return a <= eps && a >= -eps; }
template <class T>
void geti(T &a) {
  a = 0;
  int b = 0;
  char c;
  while ((c = getchar()) == ' ' || c == '\n')
    ;
  if (c == '-')
    b = 1;
  else
    a = c - 48;
  while ((c = getchar()) != ' ' && c != '\n') a = a * 10 + c - 48;
  if (b) a = -a;
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 111111;
const int M = 1111111;
const int K = 20;
const long long md = inf;
int test;
int n, m, k;
long long ans;
int a[N], cnt[N];
int cur[N];
int check() {
  for (int i = 1; i <= n; i++) cnt[a[i]]++;
  int t = 0;
  for (int i = 1; i <= n; i++)
    if (cnt[i] & 1) t++;
  return t <= 1;
}
long long getans() {
  if (!check()) return 0;
  k = 1;
  while (a[k] == a[n + 1 - k] && k * 2 < n + 1) cnt[a[k++]] -= 2;
  if (k * 2 > n) return 1LL * n * (n + 1) / 2;
  long long ret = 1LL * k * k;
  memset(cur, 0, sizeof(cur));
  for (int i = k;; i++) {
    cur[a[i]]++;
    int flag;
    if (i * 2 < n + 1)
      flag = cur[a[i]] * 2 <= cnt[a[i]];
    else if (i * 2 == n + 1)
      flag = cnt[a[i]] & 1;
    else
      flag = a[i] == a[n + 1 - i];
    if (flag)
      ret += k;
    else
      break;
  }
  memset(cur, 0, sizeof(cur));
  for (int i = n + 1 - k;; i--) {
    cur[a[i]]++;
    int flag;
    if (i * 2 > n + 1)
      flag = cur[a[i]] * 2 <= cnt[a[i]];
    else if (i * 2 == n + 1)
      flag = cnt[a[i]] & 1;
    else
      flag = a[i] == a[n + 1 - i];
    if (flag)
      ret += k;
    else
      break;
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  ans = getans();
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int inf = 1000000007;
const long long linf = 1000000000000000000LL;
const unsigned long long ulinf = (1ULL << 63) - 10ULL;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T a) {
  return a >= 0 ? a : -a;
}
template <class T>
int sign(T a) {
  return a > eps ? 1 : a < -eps ? -1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  T ret = a % b;
  if (ret < 0) ret += b;
  return ret;
}
template <class T>
T lowbit(T x) {
  return x & -x;
}
long long addmod(long long a, long long b, long long c) {
  return ((a + b) % c + c) % c;
}
long long mulmod(long long a, long long b, long long c) {
  if (b == 0LL) return 0LL;
  long long ret = mulmod(a, b >> 1, c);
  ret = (ret + ret) % c;
  if (b & 1LL) ret = (ret + a) % c;
  return ret;
}
long long powmod(long long a, long long b, long long c) {
  if (b == 0LL) return 1LL;
  long long ret = powmod(a, b >> 1, c);
  ret = ret * ret % c;
  if (b & 1LL) ret = ret * a % c;
  return ret;
}
long long modinv(long long a, long long b) { return powmod(a, b - 2LL, b); }
template <class T>
void maxe(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
void mine(T &a, T b) {
  if (a > b) a = b;
}
int iszero(double a) { return a <= eps && a >= -eps; }
template <class T>
void geti(T &a) {
  a = 0;
  int b = 0;
  char c;
  while ((c = getchar()) == ' ' || c == '\n')
    ;
  if (c == '-')
    b = 1;
  else
    a = c - 48;
  while ((c = getchar()) != ' ' && c != '\n') a = a * 10 + c - 48;
  if (b) a = -a;
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 111111;
const int M = 1111111;
const int K = 20;
const long long md = inf;
int test;
int n, m, k;
long long ans;
int a[N], cnt[N];
int cur[N];
int check() {
  for (int i = 1; i <= n; i++) cnt[a[i]]++;
  int t = 0;
  for (int i = 1; i <= n; i++)
    if (cnt[i] & 1) t++;
  return t <= 1;
}
long long getans() {
  if (!check()) return 0;
  k = 1;
  while (a[k] == a[n + 1 - k] && k * 2 < n + 1) cnt[a[k++]] -= 2;
  if (k * 2 > n) return 1LL * n * (n + 1) / 2;
  long long ret = 1LL * k * k;
  memset(cur, 0, sizeof(cur));
  for (int i = k;; i++) {
    cur[a[i]]++;
    int flag;
    if (i * 2 < n + 1)
      flag = cur[a[i]] * 2 <= cnt[a[i]];
    else if (i * 2 == n + 1)
      flag = cnt[a[i]] & 1;
    else
      flag = a[i] == a[n + 1 - i];
    if (flag)
      ret += k;
    else
      break;
  }
  memset(cur, 0, sizeof(cur));
  for (int i = n + 1 - k;; i--) {
    cur[a[i]]++;
    int flag;
    if (i * 2 > n + 1)
      flag = cur[a[i]] * 2 <= cnt[a[i]];
    else if (i * 2 == n + 1)
      flag = cnt[a[i]] & 1;
    else
      flag = a[i] == a[n + 1 - i];
    if (flag)
      ret += k;
    else
      break;
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  ans = getans();
  printf("%I64d\n", ans);
  return 0;
}

```