#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
  if (S == T) {
    T = (S = buf) + fread(buf, 1, SIZE, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
}  // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
  fwrite(buf, 1, S - buf, stdout);
  S = buf;
}
inline void putchar(char c) {
  *S++ = c;
  if (S == T) flush();
}
struct NTR {
  ~NTR() { flush(); }
} ztr;
}  // namespace Fwrite
namespace Fastio {
struct Reader {
  template <typename T>
  Reader& operator>>(T& x) {
    char c = Fread ::getchar();
    T f = 1;
    while (c < '0' || c > '9') {
      if (c == '-') f = -1;
      c = Fread ::getchar();
    }
    x = 0;
    while (c >= '0' && c <= '9') {
      x = x * 10 + (c - '0');
      c = Fread ::getchar();
    }
    x *= f;
    return *this;
  }
  Reader& operator>>(char& c) {
    c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    return *this;
  }
  Reader& operator>>(char* str) {
    int len = 0;
    char c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    while (c != '\n' && c != ' ') {
      str[len++] = c;
      c = Fread ::getchar();
    }
    str[len] = '\0';
    return *this;
  }
  Reader() {}
} cin;
const char endl = '\n';
struct Writer {
  template <typename T>
  Writer& operator<<(T x) {
    if (x == 0) {
      Fwrite ::putchar('0');
      return *this;
    }
    if (x < 0) {
      Fwrite ::putchar('-');
      x = -x;
    }
    static int sta[45];
    int top = 0;
    while (x) {
      sta[++top] = x % 10;
      x /= 10;
    }
    while (top) {
      Fwrite ::putchar(sta[top] + '0');
      --top;
    }
    return *this;
  }
  Writer& operator<<(char c) {
    Fwrite ::putchar(c);
    return *this;
  }
  Writer& operator<<(char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer& operator<<(const char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer() {}
} cout;
}  // namespace Fastio
const int MAXN = 1e5;
unsigned long long Rand() {
  return ((unsigned long long)rand() << 45) ^
         ((unsigned long long)rand() << 30) ^
         ((unsigned long long)rand() << 15) ^ ((unsigned long long)rand());
}
int n, a[MAXN + 5];
int v_odd;
vector<int> app[MAXN + 5];
int lim_r[MAXN + 5], lim_l[MAXN + 5];
int palindrome_from_mid, palindrome_from_side;
long long ans;
unsigned long long hash_w[MAXN + 5];
unsigned long long hash_sum[MAXN + 5];
bool same_multiset(int l1, int r1, int l2, int r2) {
  return hash_sum[r1] - hash_sum[l1 - 1] == hash_sum[r2] - hash_sum[l2 - 1];
}
void init_hash() {
  map<unsigned long long, bool> vis;
  for (int i = 1; i <= n; ++i) {
    hash_w[i] = Rand();
    while (vis[hash_w[i]]) hash_w[i] = Rand();
    vis[hash_w[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    hash_sum[i] = hash_sum[i - 1] + hash_w[a[i]];
  }
}
void init_lim() {
  int p = n + 1;
  while (p - 1 >= n - n / 2 + 1) {
    int v = a[p - 1];
    int t = lower_bound(app[v].begin(), app[v].end(), p - 1) - app[v].begin();
    if (t >= ((int)(app[v]).size()) - t) {
      --p;
    } else {
      break;
    }
  }
  lim_r[0] = p;
  for (int i = 1; i < n / 2; ++i) {
    int v = a[i];
    int t3 =
        lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
    int t2 = lower_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
    int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
    if (t2 - t1 < t3 - t2) {
      assert(a[i] != a[n - i + 1]);
      int t = lower_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
      assert(t < ((int)(app[v]).size()) && app[v][t] <= n - i);
      p = app[v][t] + 1;
      lim_r[i] = p;
      continue;
    }
    if (p - 1 >= n - n / 2 + 1 && a[p - 1] == a[n - i + 1]) {
      int v = a[p - 1];
      int t3 =
          lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
      int t2 =
          lower_bound(app[v].begin(), app[v].end(), p - 1) - app[v].begin();
      int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
      if (t2 - t1 >= t3 - t2) {
        --p;
      }
    }
    lim_r[i] = p;
  }
  p = 0;
  while (p + 1 <= n / 2) {
    int v = a[p + 1];
    int t = upper_bound(app[v].begin(), app[v].end(), p + 1) - app[v].begin();
    if (t <= ((int)(app[v]).size()) - t) {
      ++p;
    } else {
      break;
    }
  }
  lim_l[0] = p;
  for (int i = 1; i < n / 2; ++i) {
    int v = a[n - i + 1];
    int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
    int t2 = upper_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
    int t3 =
        lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
    if (t2 - t1 > t3 - t2) {
      assert(a[i] != a[n - i + 1]);
      int t = upper_bound(app[v].begin(), app[v].end(), p) - app[v].begin() - 1;
      assert(t >= 0 && app[v][t] > i);
      p = app[v][t] - 1;
      lim_l[i] = p;
      continue;
    }
    if (p + 1 <= n / 2 && a[p + 1] == a[i]) {
      int v = a[p + 1];
      int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
      int t2 =
          upper_bound(app[v].begin(), app[v].end(), p + 1) - app[v].begin();
      int t3 =
          lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
      if (t2 - t1 <= t3 - t2) {
        ++p;
      }
    }
    lim_l[i] = p;
  }
}
bool mid_ok;
bool check(int l, int r) {
  if (r <= n / 2) {
    return mid_ok && n / 2 - r <= palindrome_from_mid &&
           l - 1 <= palindrome_from_side &&
           same_multiset(l, r, n - r + 1, n - l + 1);
  }
  if (l >= n - n / 2 + 1) {
    return mid_ok && l - (n - n / 2 + 1) <= palindrome_from_mid &&
           n - r <= palindrome_from_side &&
           same_multiset(l, r, n - r + 1, n - l + 1);
  }
  if (l - 1 == n - r) {
    return l - 1 <= palindrome_from_side;
  } else if (l - 1 < n - r) {
    return l - 1 <= palindrome_from_side && r + 1 >= lim_r[l - 1];
  } else {
    return n - r <= palindrome_from_side && l - 1 <= lim_l[n - r];
  }
}
int main() {
  srand((unsigned long long)time(0) ^ (unsigned long long)(new char));
  Fastio ::cin >> n;
  for (int i = 1; i <= n; ++i) {
    Fastio ::cin >> a[i];
    app[a[i]].push_back(i);
  }
  v_odd = 0;
  for (int i = 1; i <= n; ++i) {
    if (((int)(app[i]).size()) & 1) {
      if (v_odd) {
        Fastio ::cout << 0 << Fastio ::endl;
        return 0;
      }
      v_odd = i;
    }
  }
  if (n % 2 == 0) {
    assert(!v_odd);
    mid_ok = 1;
  } else {
    assert(v_odd);
    mid_ok = (a[n / 2 + 1] == v_odd);
  }
  init_hash();
  init_lim();
  palindrome_from_mid = 0;
  while (palindrome_from_mid < n / 2 &&
         a[n / 2 - palindrome_from_mid] ==
             a[n - n / 2 + 1 + palindrome_from_mid]) {
    ++palindrome_from_mid;
  }
  palindrome_from_side = 0;
  while (palindrome_from_side < n / 2 &&
         a[palindrome_from_side + 1] == a[n - palindrome_from_side]) {
    ++palindrome_from_side;
  }
  for (int i = 1; i <= n; ++i) {
    int l = 0, r = i;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid, i)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    ans += l;
  }
  Fastio ::cout << ans << Fastio ::endl;
  return 0;
}

### Prompt

Your task is to create 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;
template <typename T>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
  if (S == T) {
    T = (S = buf) + fread(buf, 1, SIZE, stdin);
    if (S == T) return '\n';
  }
  return *S++;
}
}  // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
  fwrite(buf, 1, S - buf, stdout);
  S = buf;
}
inline void putchar(char c) {
  *S++ = c;
  if (S == T) flush();
}
struct NTR {
  ~NTR() { flush(); }
} ztr;
}  // namespace Fwrite
namespace Fastio {
struct Reader {
  template <typename T>
  Reader& operator>>(T& x) {
    char c = Fread ::getchar();
    T f = 1;
    while (c < '0' || c > '9') {
      if (c == '-') f = -1;
      c = Fread ::getchar();
    }
    x = 0;
    while (c >= '0' && c <= '9') {
      x = x * 10 + (c - '0');
      c = Fread ::getchar();
    }
    x *= f;
    return *this;
  }
  Reader& operator>>(char& c) {
    c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    return *this;
  }
  Reader& operator>>(char* str) {
    int len = 0;
    char c = Fread ::getchar();
    while (c == '\n' || c == ' ') c = Fread ::getchar();
    while (c != '\n' && c != ' ') {
      str[len++] = c;
      c = Fread ::getchar();
    }
    str[len] = '\0';
    return *this;
  }
  Reader() {}
} cin;
const char endl = '\n';
struct Writer {
  template <typename T>
  Writer& operator<<(T x) {
    if (x == 0) {
      Fwrite ::putchar('0');
      return *this;
    }
    if (x < 0) {
      Fwrite ::putchar('-');
      x = -x;
    }
    static int sta[45];
    int top = 0;
    while (x) {
      sta[++top] = x % 10;
      x /= 10;
    }
    while (top) {
      Fwrite ::putchar(sta[top] + '0');
      --top;
    }
    return *this;
  }
  Writer& operator<<(char c) {
    Fwrite ::putchar(c);
    return *this;
  }
  Writer& operator<<(char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer& operator<<(const char* str) {
    int cur = 0;
    while (str[cur]) Fwrite ::putchar(str[cur++]);
    return *this;
  }
  Writer() {}
} cout;
}  // namespace Fastio
const int MAXN = 1e5;
unsigned long long Rand() {
  return ((unsigned long long)rand() << 45) ^
         ((unsigned long long)rand() << 30) ^
         ((unsigned long long)rand() << 15) ^ ((unsigned long long)rand());
}
int n, a[MAXN + 5];
int v_odd;
vector<int> app[MAXN + 5];
int lim_r[MAXN + 5], lim_l[MAXN + 5];
int palindrome_from_mid, palindrome_from_side;
long long ans;
unsigned long long hash_w[MAXN + 5];
unsigned long long hash_sum[MAXN + 5];
bool same_multiset(int l1, int r1, int l2, int r2) {
  return hash_sum[r1] - hash_sum[l1 - 1] == hash_sum[r2] - hash_sum[l2 - 1];
}
void init_hash() {
  map<unsigned long long, bool> vis;
  for (int i = 1; i <= n; ++i) {
    hash_w[i] = Rand();
    while (vis[hash_w[i]]) hash_w[i] = Rand();
    vis[hash_w[i]] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    hash_sum[i] = hash_sum[i - 1] + hash_w[a[i]];
  }
}
void init_lim() {
  int p = n + 1;
  while (p - 1 >= n - n / 2 + 1) {
    int v = a[p - 1];
    int t = lower_bound(app[v].begin(), app[v].end(), p - 1) - app[v].begin();
    if (t >= ((int)(app[v]).size()) - t) {
      --p;
    } else {
      break;
    }
  }
  lim_r[0] = p;
  for (int i = 1; i < n / 2; ++i) {
    int v = a[i];
    int t3 =
        lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
    int t2 = lower_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
    int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
    if (t2 - t1 < t3 - t2) {
      assert(a[i] != a[n - i + 1]);
      int t = lower_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
      assert(t < ((int)(app[v]).size()) && app[v][t] <= n - i);
      p = app[v][t] + 1;
      lim_r[i] = p;
      continue;
    }
    if (p - 1 >= n - n / 2 + 1 && a[p - 1] == a[n - i + 1]) {
      int v = a[p - 1];
      int t3 =
          lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
      int t2 =
          lower_bound(app[v].begin(), app[v].end(), p - 1) - app[v].begin();
      int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
      if (t2 - t1 >= t3 - t2) {
        --p;
      }
    }
    lim_r[i] = p;
  }
  p = 0;
  while (p + 1 <= n / 2) {
    int v = a[p + 1];
    int t = upper_bound(app[v].begin(), app[v].end(), p + 1) - app[v].begin();
    if (t <= ((int)(app[v]).size()) - t) {
      ++p;
    } else {
      break;
    }
  }
  lim_l[0] = p;
  for (int i = 1; i < n / 2; ++i) {
    int v = a[n - i + 1];
    int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
    int t2 = upper_bound(app[v].begin(), app[v].end(), p) - app[v].begin();
    int t3 =
        lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
    if (t2 - t1 > t3 - t2) {
      assert(a[i] != a[n - i + 1]);
      int t = upper_bound(app[v].begin(), app[v].end(), p) - app[v].begin() - 1;
      assert(t >= 0 && app[v][t] > i);
      p = app[v][t] - 1;
      lim_l[i] = p;
      continue;
    }
    if (p + 1 <= n / 2 && a[p + 1] == a[i]) {
      int v = a[p + 1];
      int t1 = upper_bound(app[v].begin(), app[v].end(), i) - app[v].begin();
      int t2 =
          upper_bound(app[v].begin(), app[v].end(), p + 1) - app[v].begin();
      int t3 =
          lower_bound(app[v].begin(), app[v].end(), n - i + 1) - app[v].begin();
      if (t2 - t1 <= t3 - t2) {
        ++p;
      }
    }
    lim_l[i] = p;
  }
}
bool mid_ok;
bool check(int l, int r) {
  if (r <= n / 2) {
    return mid_ok && n / 2 - r <= palindrome_from_mid &&
           l - 1 <= palindrome_from_side &&
           same_multiset(l, r, n - r + 1, n - l + 1);
  }
  if (l >= n - n / 2 + 1) {
    return mid_ok && l - (n - n / 2 + 1) <= palindrome_from_mid &&
           n - r <= palindrome_from_side &&
           same_multiset(l, r, n - r + 1, n - l + 1);
  }
  if (l - 1 == n - r) {
    return l - 1 <= palindrome_from_side;
  } else if (l - 1 < n - r) {
    return l - 1 <= palindrome_from_side && r + 1 >= lim_r[l - 1];
  } else {
    return n - r <= palindrome_from_side && l - 1 <= lim_l[n - r];
  }
}
int main() {
  srand((unsigned long long)time(0) ^ (unsigned long long)(new char));
  Fastio ::cin >> n;
  for (int i = 1; i <= n; ++i) {
    Fastio ::cin >> a[i];
    app[a[i]].push_back(i);
  }
  v_odd = 0;
  for (int i = 1; i <= n; ++i) {
    if (((int)(app[i]).size()) & 1) {
      if (v_odd) {
        Fastio ::cout << 0 << Fastio ::endl;
        return 0;
      }
      v_odd = i;
    }
  }
  if (n % 2 == 0) {
    assert(!v_odd);
    mid_ok = 1;
  } else {
    assert(v_odd);
    mid_ok = (a[n / 2 + 1] == v_odd);
  }
  init_hash();
  init_lim();
  palindrome_from_mid = 0;
  while (palindrome_from_mid < n / 2 &&
         a[n / 2 - palindrome_from_mid] ==
             a[n - n / 2 + 1 + palindrome_from_mid]) {
    ++palindrome_from_mid;
  }
  palindrome_from_side = 0;
  while (palindrome_from_side < n / 2 &&
         a[palindrome_from_side + 1] == a[n - palindrome_from_side]) {
    ++palindrome_from_side;
  }
  for (int i = 1; i <= n; ++i) {
    int l = 0, r = i;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid, i)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    ans += l;
  }
  Fastio ::cout << ans << Fastio ::endl;
  return 0;
}

```