#include <bits/stdc++.h>
using namespace std;
long long a[100010];
long long cant[100010];
long long k, n;
bool isinclude(long long mid) {
  vector<long long> v(100003, 0);
  vector<long long> w(100003, 0);
  if (mid - k >= n - k - mid) {
    for (long long i = k; i < mid; i++) v[a[i]]++;
    for (long long i = mid; i < n - k; i++) w[a[i]]++;
    bool contenido = 1;
    for (long long i = 0; i < 100003; i++)
      if (w[i] > v[i]) {
        contenido = 0;
        break;
      }
    return contenido;
  }
  bool todook = 1;
  bool morado = 1;
  for (long long i = n - k - 1; i >= n - mid; i--) w[a[i]]++;
  for (long long i = k; i <= mid - 1; i++) v[a[i]]++;
  for (long long i = mid; i < n - mid; i++)
    if (i < n - 1 - i && a[i] != a[n - 1 - i]) todook = 0;
  for (long long i = 0; i < 100003; i++)
    if (v[i] != w[i]) morado = 0;
  return morado && todook;
}
bool isinclude_2(long long mid) {
  vector<long long> v(100003, 0);
  vector<long long> w(100003, 0);
  if (n - k - mid - 1 >= mid - k + 1) {
    for (long long i = k; i <= mid; i++) v[a[i]]++;
    for (long long i = mid + 1; i < n - k; i++) w[a[i]]++;
    bool contenido = 1;
    for (int i = 0; i < 100003; i++)
      if (v[i] > w[i]) {
        contenido = 0;
        break;
      }
    return contenido;
  }
  bool todobom = 1;
  bool morado = 1;
  for (long long i = k; i < n - mid - 1; i++) v[a[i]]++;
  for (long long i = mid + 1; i < n - k; i++) w[a[i]]++;
  for (long long i = n - mid; i < mid; i++)
    if (i < n - 1 - i && a[i] != a[n - 1 - i]) todobom = 0;
  for (long long i = 0; i < 100003; i++)
    if (v[i] != w[i]) {
      morado = 0;
      break;
    }
  return morado && todobom;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  k = 0;
  for (long long i = 0; i < n; i++) {
    if (i < n - 1 - i && a[i] == a[n - 1 - i])
      k = i + 1;
    else
      break;
  }
  bool es = 1;
  bool okini = 1;
  for (long long i = k; i < n - k; i++) cant[a[i]]++;
  long long total = 0;
  for (long long i = 0; i < 100010; i++)
    if (cant[i] % 2 == 1) total++;
  if (total >= 2) es = 0;
  long long ans1 = 0;
  long long ans2 = 0;
  long long lo1 = k, hi1 = n - k - 1;
  while (lo1 < hi1) {
    long long mid = (lo1 + hi1) / 2;
    if (isinclude(mid))
      hi1 = mid;
    else
      lo1 = mid + 1;
  }
  ans1 = n - lo1 - k + 1;
  long long lo2 = k, hi2 = n - k - 1;
  while (lo2 < hi2) {
    long long mid = (lo2 + hi2 + 1) / 2;
    if (isinclude_2(mid))
      lo2 = mid;
    else
      hi2 = mid - 1;
  }
  ans2 = lo2 - k + 2;
  long long res = 0;
  if (es) res = (ans1 + ans2 - 1) + k * (ans1 + ans2) + k * k;
  if ((n - 2 * k) <= 1) res = n * (n + 1) / 2;
  cout << res << endl;
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
long long a[100010];
long long cant[100010];
long long k, n;
bool isinclude(long long mid) {
  vector<long long> v(100003, 0);
  vector<long long> w(100003, 0);
  if (mid - k >= n - k - mid) {
    for (long long i = k; i < mid; i++) v[a[i]]++;
    for (long long i = mid; i < n - k; i++) w[a[i]]++;
    bool contenido = 1;
    for (long long i = 0; i < 100003; i++)
      if (w[i] > v[i]) {
        contenido = 0;
        break;
      }
    return contenido;
  }
  bool todook = 1;
  bool morado = 1;
  for (long long i = n - k - 1; i >= n - mid; i--) w[a[i]]++;
  for (long long i = k; i <= mid - 1; i++) v[a[i]]++;
  for (long long i = mid; i < n - mid; i++)
    if (i < n - 1 - i && a[i] != a[n - 1 - i]) todook = 0;
  for (long long i = 0; i < 100003; i++)
    if (v[i] != w[i]) morado = 0;
  return morado && todook;
}
bool isinclude_2(long long mid) {
  vector<long long> v(100003, 0);
  vector<long long> w(100003, 0);
  if (n - k - mid - 1 >= mid - k + 1) {
    for (long long i = k; i <= mid; i++) v[a[i]]++;
    for (long long i = mid + 1; i < n - k; i++) w[a[i]]++;
    bool contenido = 1;
    for (int i = 0; i < 100003; i++)
      if (v[i] > w[i]) {
        contenido = 0;
        break;
      }
    return contenido;
  }
  bool todobom = 1;
  bool morado = 1;
  for (long long i = k; i < n - mid - 1; i++) v[a[i]]++;
  for (long long i = mid + 1; i < n - k; i++) w[a[i]]++;
  for (long long i = n - mid; i < mid; i++)
    if (i < n - 1 - i && a[i] != a[n - 1 - i]) todobom = 0;
  for (long long i = 0; i < 100003; i++)
    if (v[i] != w[i]) {
      morado = 0;
      break;
    }
  return morado && todobom;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  k = 0;
  for (long long i = 0; i < n; i++) {
    if (i < n - 1 - i && a[i] == a[n - 1 - i])
      k = i + 1;
    else
      break;
  }
  bool es = 1;
  bool okini = 1;
  for (long long i = k; i < n - k; i++) cant[a[i]]++;
  long long total = 0;
  for (long long i = 0; i < 100010; i++)
    if (cant[i] % 2 == 1) total++;
  if (total >= 2) es = 0;
  long long ans1 = 0;
  long long ans2 = 0;
  long long lo1 = k, hi1 = n - k - 1;
  while (lo1 < hi1) {
    long long mid = (lo1 + hi1) / 2;
    if (isinclude(mid))
      hi1 = mid;
    else
      lo1 = mid + 1;
  }
  ans1 = n - lo1 - k + 1;
  long long lo2 = k, hi2 = n - k - 1;
  while (lo2 < hi2) {
    long long mid = (lo2 + hi2 + 1) / 2;
    if (isinclude_2(mid))
      lo2 = mid;
    else
      hi2 = mid - 1;
  }
  ans2 = lo2 - k + 2;
  long long res = 0;
  if (es) res = (ans1 + ans2 - 1) + k * (ans1 + ans2) + k * k;
  if ((n - 2 * k) <= 1) res = n * (n + 1) / 2;
  cout << res << endl;
  return 0;
}

```