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.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template <class T>
int size(T &&x) {
  return int(x.size());
}
template <class A, class B>
ostream &operator<<(ostream &out, const pair<A, B> &p) {
  return out << '(' << p.first << ", " << p.second << ')';
}
template <class T>
auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
  out << '{';
  for (auto it = x.begin(); it != x.end(); ++it)
    out << *it << (it == prev(x.end()) ? "" : ", ");
  return out << '}';
}
void dump() {}
template <class T, class... Args>
void dump(T &&x, Args... args) {
  cerr << x << ";  ";
  dump(args...);
}
mt19937_64 rng(0);
int rd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &ai : a) {
    cin >> ai;
    --ai;
  }
  vector<int> delta(n);
  int cnt_nprz = 0, cnt_negative = 0, cnt_nonequal = 0;
  int L = 0, R = -1;
  auto inside = [&](int i) { return L <= i and i <= R; };
  auto consider = [&](int i, bool to_add) {
    0 && cerr;
    if (i < 0 or i >= n) return;
    int j = n - 1 - i;
    int sign_to_add = (to_add ? 1 : -1);
    if (not inside(i) and not inside(j)) {
      if (a[i] != a[j]) cnt_nonequal += sign_to_add;
      return;
    }
    auto consider_delta = [&](int k) {
      if (delta[a[k]] < 0) --cnt_negative;
      if (delta[a[k]] % 2 == 1) --cnt_nprz;
      delta[a[k]] += (inside(k) ? 1 : -1) * sign_to_add;
      if (delta[a[k]] < 0) ++cnt_negative;
      if (delta[a[k]] % 2 == 1) ++cnt_nprz;
    };
    consider_delta(i);
    if (i != j) consider_delta(j);
  };
  auto is_good = [&] {
    return cnt_nonequal == 0 and cnt_negative == 0 and cnt_nprz <= 1;
  };
  auto print_state = [&] { 0 && cerr; };
  for (int i = (0); i <= (((n + 1) / 2) - 1); ++i) consider(i, true);
  print_state();
  auto move_R_right = [&] {
    consider(R + 1, false);
    consider(++R, true);
  };
  auto move_L_right = [&] {
    consider(L, false);
    ++L;
    consider(L - 1, true);
  };
  LL answer = 0;
  for (; L != n; move_L_right()) {
    if (R < L) move_R_right();
    while (R != n and not is_good()) {
      move_R_right();
      print_state();
    }
    0 && cerr;
    answer += n - R;
  }
  cout << answer << '\n';
}
