#include <bits/stdc++.h>
using namespace std;
const long double pi = 3.1415926535897932384626433832795l;
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T1, typename T2>
inline bool umx(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1& a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 100000;
struct Input {
  int n;
  int a[N];
  bool read() {
    if (!(cin >> n)) {
      return 0;
    }
    for (int i = int(0); i < int(n); ++i) {
      scanf("%d", &a[i]);
      --a[i];
    }
    return 1;
  }
  void init(const Input& input) { *this = input; }
};
struct Data : Input {
  long long ans;
  void write() { cout << ans << endl; }
  virtual void solve() {}
  virtual void clear() { *this = Data(); }
};
struct Solution : Data {
  int l, r;
  int bad[N];
  int sum[N + 1];
  int cnt1[N], cnt2[N], cnt3[N], cnt4[N];
  int bad2, bad3, bad3_, bad4, bad4_;
  int cntbad2(int x) { return cnt1[x] != cnt2[x]; }
  int cntbad3(int x) { return cnt1[x] < cnt3[x]; }
  int cntbad3_(int x) { return (cnt1[x] - cnt3[x]) % 2 != 0; }
  int cntbad4(int x) { return cnt1[x] < cnt4[x]; }
  int cntbad4_(int x) { return (cnt1[x] - cnt4[x]) % 2 != 0; }
  bool check() {
    if (r <= n / 2) {
      return sum[l] == 0 && sum[n - r] - sum[r] == 0 && bad2 == 0;
    }
    if (n - l <= n / 2) {
      return sum[n - r] == 0 && sum[l] - sum[n - l] == 0 && bad2 == 0;
    }
    if (l < n - r) {
      return sum[l] == 0 && bad3 == 0 && bad3_ <= 1;
    } else {
      return sum[n - r] == 0 && bad4 == 0 && bad4_ <= 1;
    }
  }
  void solve() {
    ans = 0;
    bad2 = bad3 = bad3_ = bad4 = bad4_ = 0;
    sum[0] = 0;
    for (int i = int(0); i < int(n); ++i) {
      bad[i] = a[i] != a[n - 1 - i];
      sum[i + 1] = sum[i] + bad[i];
    }
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    memset(cnt3, 0, sizeof cnt3);
    memset(cnt4, 0, sizeof cnt4);
    for (int i = int(0); i < int(n); ++i) {
      cnt3[a[i]]++;
      cnt4[a[i]]--;
    }
    for (int i = int(0); i < int(n); ++i) {
      bad2 += cntbad2(i);
      bad3 += cntbad3(i);
      bad3_ += cntbad3_(i);
      bad4 += cntbad4(i);
      bad4_ += cntbad4_(i);
    }
    r = 0;
    for (l = 0; l < n; ++l) {
      while (r <= l || !check()) {
        if (r == n) {
          return;
        }
        bad2 -= cntbad2(a[r]);
        bad3 -= cntbad3(a[r]);
        bad3_ -= cntbad3_(a[r]);
        bad4 -= cntbad4(a[r]);
        bad4_ -= cntbad4_(a[r]);
        if (bad[r]) {
          bad2 -= cntbad2(a[n - 1 - r]);
          bad3 -= cntbad3(a[n - 1 - r]);
          bad3_ -= cntbad3_(a[n - 1 - r]);
          bad4 -= cntbad4(a[n - 1 - r]);
          bad4_ -= cntbad4_(a[n - 1 - r]);
        }
        cnt1[a[r]]++;
        cnt2[a[n - 1 - r]]++;
        cnt3[a[r]]--;
        cnt4[a[n - 1 - r]]++;
        bad2 += cntbad2(a[r]);
        bad3 += cntbad3(a[r]);
        bad3_ += cntbad3_(a[r]);
        bad4 += cntbad4(a[r]);
        bad4_ += cntbad4_(a[r]);
        if (bad[r]) {
          bad2 += cntbad2(a[n - 1 - r]);
          bad3 += cntbad3(a[n - 1 - r]);
          bad3_ += cntbad3_(a[n - 1 - r]);
          bad4 += cntbad4(a[n - 1 - r]);
          bad4_ += cntbad4_(a[n - 1 - r]);
        }
        ++r;
      };
      ans += n - r + 1;
      bad2 -= cntbad2(a[l]);
      bad3 -= cntbad3(a[l]);
      bad3_ -= cntbad3_(a[l]);
      bad4 -= cntbad4(a[l]);
      bad4_ -= cntbad4_(a[l]);
      if (bad[l]) {
        bad2 -= cntbad2(a[n - 1 - l]);
        bad3 -= cntbad3(a[n - 1 - l]);
        bad3_ -= cntbad3_(a[n - 1 - l]);
        bad4 -= cntbad4(a[n - 1 - l]);
        bad4_ -= cntbad4_(a[n - 1 - l]);
      }
      cnt1[a[l]]--;
      cnt2[a[n - 1 - l]]--;
      cnt3[a[n - 1 - l]]--;
      cnt4[a[l]]++;
      bad2 += cntbad2(a[l]);
      bad3 += cntbad3(a[l]);
      bad3_ += cntbad3_(a[l]);
      bad4 += cntbad4(a[l]);
      bad4_ += cntbad4_(a[l]);
      if (bad[l]) {
        bad2 += cntbad2(a[n - 1 - l]);
        bad3 += cntbad3(a[n - 1 - l]);
        bad3_ += cntbad3_(a[n - 1 - l]);
        bad4 += cntbad4(a[n - 1 - l]);
        bad4_ += cntbad4_(a[n - 1 - l]);
      }
    }
  }
  void clear() { *this = Solution(); }
};
Solution sol;
int main() {
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}

### Prompt

Please formulate 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;
const long double pi = 3.1415926535897932384626433832795l;
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T1, typename T2>
inline bool umx(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1& a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 100000;
struct Input {
  int n;
  int a[N];
  bool read() {
    if (!(cin >> n)) {
      return 0;
    }
    for (int i = int(0); i < int(n); ++i) {
      scanf("%d", &a[i]);
      --a[i];
    }
    return 1;
  }
  void init(const Input& input) { *this = input; }
};
struct Data : Input {
  long long ans;
  void write() { cout << ans << endl; }
  virtual void solve() {}
  virtual void clear() { *this = Data(); }
};
struct Solution : Data {
  int l, r;
  int bad[N];
  int sum[N + 1];
  int cnt1[N], cnt2[N], cnt3[N], cnt4[N];
  int bad2, bad3, bad3_, bad4, bad4_;
  int cntbad2(int x) { return cnt1[x] != cnt2[x]; }
  int cntbad3(int x) { return cnt1[x] < cnt3[x]; }
  int cntbad3_(int x) { return (cnt1[x] - cnt3[x]) % 2 != 0; }
  int cntbad4(int x) { return cnt1[x] < cnt4[x]; }
  int cntbad4_(int x) { return (cnt1[x] - cnt4[x]) % 2 != 0; }
  bool check() {
    if (r <= n / 2) {
      return sum[l] == 0 && sum[n - r] - sum[r] == 0 && bad2 == 0;
    }
    if (n - l <= n / 2) {
      return sum[n - r] == 0 && sum[l] - sum[n - l] == 0 && bad2 == 0;
    }
    if (l < n - r) {
      return sum[l] == 0 && bad3 == 0 && bad3_ <= 1;
    } else {
      return sum[n - r] == 0 && bad4 == 0 && bad4_ <= 1;
    }
  }
  void solve() {
    ans = 0;
    bad2 = bad3 = bad3_ = bad4 = bad4_ = 0;
    sum[0] = 0;
    for (int i = int(0); i < int(n); ++i) {
      bad[i] = a[i] != a[n - 1 - i];
      sum[i + 1] = sum[i] + bad[i];
    }
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    memset(cnt3, 0, sizeof cnt3);
    memset(cnt4, 0, sizeof cnt4);
    for (int i = int(0); i < int(n); ++i) {
      cnt3[a[i]]++;
      cnt4[a[i]]--;
    }
    for (int i = int(0); i < int(n); ++i) {
      bad2 += cntbad2(i);
      bad3 += cntbad3(i);
      bad3_ += cntbad3_(i);
      bad4 += cntbad4(i);
      bad4_ += cntbad4_(i);
    }
    r = 0;
    for (l = 0; l < n; ++l) {
      while (r <= l || !check()) {
        if (r == n) {
          return;
        }
        bad2 -= cntbad2(a[r]);
        bad3 -= cntbad3(a[r]);
        bad3_ -= cntbad3_(a[r]);
        bad4 -= cntbad4(a[r]);
        bad4_ -= cntbad4_(a[r]);
        if (bad[r]) {
          bad2 -= cntbad2(a[n - 1 - r]);
          bad3 -= cntbad3(a[n - 1 - r]);
          bad3_ -= cntbad3_(a[n - 1 - r]);
          bad4 -= cntbad4(a[n - 1 - r]);
          bad4_ -= cntbad4_(a[n - 1 - r]);
        }
        cnt1[a[r]]++;
        cnt2[a[n - 1 - r]]++;
        cnt3[a[r]]--;
        cnt4[a[n - 1 - r]]++;
        bad2 += cntbad2(a[r]);
        bad3 += cntbad3(a[r]);
        bad3_ += cntbad3_(a[r]);
        bad4 += cntbad4(a[r]);
        bad4_ += cntbad4_(a[r]);
        if (bad[r]) {
          bad2 += cntbad2(a[n - 1 - r]);
          bad3 += cntbad3(a[n - 1 - r]);
          bad3_ += cntbad3_(a[n - 1 - r]);
          bad4 += cntbad4(a[n - 1 - r]);
          bad4_ += cntbad4_(a[n - 1 - r]);
        }
        ++r;
      };
      ans += n - r + 1;
      bad2 -= cntbad2(a[l]);
      bad3 -= cntbad3(a[l]);
      bad3_ -= cntbad3_(a[l]);
      bad4 -= cntbad4(a[l]);
      bad4_ -= cntbad4_(a[l]);
      if (bad[l]) {
        bad2 -= cntbad2(a[n - 1 - l]);
        bad3 -= cntbad3(a[n - 1 - l]);
        bad3_ -= cntbad3_(a[n - 1 - l]);
        bad4 -= cntbad4(a[n - 1 - l]);
        bad4_ -= cntbad4_(a[n - 1 - l]);
      }
      cnt1[a[l]]--;
      cnt2[a[n - 1 - l]]--;
      cnt3[a[n - 1 - l]]--;
      cnt4[a[l]]++;
      bad2 += cntbad2(a[l]);
      bad3 += cntbad3(a[l]);
      bad3_ += cntbad3_(a[l]);
      bad4 += cntbad4(a[l]);
      bad4_ += cntbad4_(a[l]);
      if (bad[l]) {
        bad2 += cntbad2(a[n - 1 - l]);
        bad3 += cntbad3(a[n - 1 - l]);
        bad3_ += cntbad3_(a[n - 1 - l]);
        bad4 += cntbad4(a[n - 1 - l]);
        bad4_ += cntbad4_(a[n - 1 - l]);
      }
    }
  }
  void clear() { *this = Solution(); }
};
Solution sol;
int main() {
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}

```