#include <bits/stdc++.h>
using namespace std;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
const long long N = 1e5 + 5;
long long t[N];
long long cnt_all[N];
long long need[N];
long long bad[N];
long long has_from_pair[N];
long long belong[N];
long long need_val[N];
long long good;
long long n;
long long bad_cnt;
long long bad_outside;
void Update(long long val, long long delta) {
  long long badd = -(need_val[val] > 0);
  need_val[val] += delta;
  badd += (need_val[val] > 0);
  bad_cnt += badd;
  good = (bad_cnt == 0 && bad_outside == 0);
}
void Add(long long pos) {
  long long para = belong[pos];
  has_from_pair[para]++;
  Update(t[pos], -1);
  long long nei = n - pos + 1;
  if (has_from_pair[para] == 2) {
    Update(t[pos], -1);
  } else {
    if (pos == n / 2 + 1 && n % 2 == 1) {
      goto A;
    }
    if (bad[para]) {
      bad_outside--;
    }
    Update(t[nei], 1);
  A:;
  }
}
void Subtract(long long pos) {
  long long para = belong[pos];
  has_from_pair[para]--;
  Update(t[pos], 1);
  long long nei = n - pos + 1;
  if (has_from_pair[para] == 0) {
    if (pos == n / 2 + 1 && n % 2 == 1) {
      goto A;
    }
    if (bad[para]) {
      bad_outside++;
    }
    Update(t[nei], -1);
  A:;
  } else {
    Update(t[pos], 1);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  cin >> n;
  for (long long i = (1); i <= (n); ++i) {
    cin >> t[i];
    cnt_all[t[i]]++;
    belong[i] = min(i, n - i + 1);
  }
  long long odd = 0;
  for (long long i = (1); i <= (n); ++i) {
    odd += cnt_all[i] % 2;
  }
  if (odd >= 2) {
    cout << 0 << "\n";
    return 0;
  }
  for (long long i = (1); i <= (n / 2); ++i) {
    if (t[i] != t[n - i + 1]) {
      bad[i] = 1;
      bad_cnt++;
    }
  }
  if (bad_cnt == 0) {
    cout << n * (n + 1) / 2 << endl;
    return 0;
  }
  bad_outside = bad_cnt;
  bad_cnt = 0;
  good = 0;
  long long res = 0;
  long long last = 0;
  for (long long i = (1); i <= (n); ++i) {
    if (last < i) {
      Add(i);
      last = i;
    }
    while (!good && last < n) {
      last++;
      Add(last);
    }
    if (good) {
      res += n - last + 1;
      ;
    }
    Subtract(i);
  }
  cout << res << "\n";
  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>
using namespace std;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
const long long N = 1e5 + 5;
long long t[N];
long long cnt_all[N];
long long need[N];
long long bad[N];
long long has_from_pair[N];
long long belong[N];
long long need_val[N];
long long good;
long long n;
long long bad_cnt;
long long bad_outside;
void Update(long long val, long long delta) {
  long long badd = -(need_val[val] > 0);
  need_val[val] += delta;
  badd += (need_val[val] > 0);
  bad_cnt += badd;
  good = (bad_cnt == 0 && bad_outside == 0);
}
void Add(long long pos) {
  long long para = belong[pos];
  has_from_pair[para]++;
  Update(t[pos], -1);
  long long nei = n - pos + 1;
  if (has_from_pair[para] == 2) {
    Update(t[pos], -1);
  } else {
    if (pos == n / 2 + 1 && n % 2 == 1) {
      goto A;
    }
    if (bad[para]) {
      bad_outside--;
    }
    Update(t[nei], 1);
  A:;
  }
}
void Subtract(long long pos) {
  long long para = belong[pos];
  has_from_pair[para]--;
  Update(t[pos], 1);
  long long nei = n - pos + 1;
  if (has_from_pair[para] == 0) {
    if (pos == n / 2 + 1 && n % 2 == 1) {
      goto A;
    }
    if (bad[para]) {
      bad_outside++;
    }
    Update(t[nei], -1);
  A:;
  } else {
    Update(t[pos], 1);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  cin >> n;
  for (long long i = (1); i <= (n); ++i) {
    cin >> t[i];
    cnt_all[t[i]]++;
    belong[i] = min(i, n - i + 1);
  }
  long long odd = 0;
  for (long long i = (1); i <= (n); ++i) {
    odd += cnt_all[i] % 2;
  }
  if (odd >= 2) {
    cout << 0 << "\n";
    return 0;
  }
  for (long long i = (1); i <= (n / 2); ++i) {
    if (t[i] != t[n - i + 1]) {
      bad[i] = 1;
      bad_cnt++;
    }
  }
  if (bad_cnt == 0) {
    cout << n * (n + 1) / 2 << endl;
    return 0;
  }
  bad_outside = bad_cnt;
  bad_cnt = 0;
  good = 0;
  long long res = 0;
  long long last = 0;
  for (long long i = (1); i <= (n); ++i) {
    if (last < i) {
      Add(i);
      last = i;
    }
    while (!good && last < n) {
      last++;
      Add(last);
    }
    if (good) {
      res += n - last + 1;
      ;
    }
    Subtract(i);
  }
  cout << res << "\n";
  return 0;
}

```