#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const long long INF = 1e9;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int readInt() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
const int mn = 1e5 + 2;
int a[mn];
vector<int> getodd(vector<int> &L, vector<int> &R) {
  map<int, int> h;
  for (auto &w : L) h[w]++;
  for (auto &w : R) h[w]++;
  vector<int> vodd;
  for (auto &w : h)
    if (w.second % 2 != 0) vodd.push_back(w.first);
  return vodd;
}
int help(vector<int> &L, vector<int> &R) {
  int lsz = L.size();
  assert(lsz == R.size());
  map<int, int> h;
  for (auto &w : L) h[w]++;
  for (auto &w : R) h[w]--;
  int excess = 0;
  for (auto &w : h) {
    if (abs(w.second) % 2 != 0) return INF;
    if (w.second > 0) excess += w.second;
  }
  if (excess <= 0) {
    return 0;
  }
  for (int i = 0; i < lsz; i++) {
    int x = L[i];
    if (h[x] >= 2) {
      h[x] -= 2;
      excess -= 2;
    }
    if (excess <= 0) {
      return i + 1;
    }
  }
  return INF;
}
int solve(vector<int> &L, vector<int> &R, int mid) {
  int final = help(L, R);
  if (final > 0 && mid != -1) final++;
  int lsz = L.size();
  if (mid != -1) {
    vector<int> vodd = getodd(L, R);
    if (vodd.size() == 2 && (vodd[0] == mid || vodd[1] == mid)) {
      int other = -1;
      for (auto &w : vodd)
        if (w != mid) other = w;
      for (int k = 0; k < 3; k++) {
        vector<int> cL = L, cR = R;
        int minidx = -1;
        if (k == 0) {
          for (int i = 0; i < lsz; i++)
            if (cL[i] == other) {
              cL[i] = mid;
              minidx = i;
              break;
            }
        } else if (k == 1) {
          for (int i = lsz - 1; lsz >= 0; lsz--)
            if (cL[i] == other) {
              cL[i] = mid;
              minidx = i;
              break;
            }
        } else {
          for (auto &w : cR)
            if (w == other) {
              w = mid;
              break;
            }
        }
        chkmin(final, max(minidx + 1, help(cL, cR)) + 1);
      }
    }
  }
  return final;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = readInt();
  for (int i = 1; i <= n; i++) a[i] = readInt();
  int l = -1, r = -1;
  int l2 = -1, r2 = -1;
  for (int i = 1; i <= n; i++) {
    if (i < n + 1 - i) {
      if (a[i] != a[n + 1 - i]) {
        l = i;
        r = n + 1 - i;
        break;
      }
    }
  }
  int ml2;
  for (int i = 1; i <= n; i++) {
    if (i < n + 1 - i) {
      if (a[i] != a[n + 1 - i]) {
        l2 = i;
        r2 = n + 1 - i;
      }
      ml2 = i;
    }
  }
  if (l == -1) {
    printf("%lld\n", ((long long)n * (long long)(n + 1LL)) / 2);
    return 0;
  }
  int whole = 0;
  long long final = 0;
  {
    bool ok = 1;
    map<int, int> h;
    for (int x = l; x <= l2; x++) h[a[x]]++;
    for (int x = r2; x <= r; x++) h[a[x]]--;
    for (auto &w : h)
      if (w.second != 0) ok = 0;
    if (ok) {
      final += 2LL * (ml2 - l2 + 1) * l;
    }
  }
  for (int t = 0; t < 2; t++) {
    vector<int> L, R;
    int midx = -1;
    if (n % 2 == 1) {
      int mid = (n + 1) / 2;
      for (int x = mid - 1; x >= l; x--) L.push_back(a[x]);
      for (int x = mid + 1; x <= r; x++) R.push_back(a[x]);
      midx = a[mid];
    } else {
      for (int x = n / 2; x >= l; x--) L.push_back(a[x]);
      for (int x = (n / 2) + 1; x <= r; x++) R.push_back(a[x]);
    }
    int needleft = max(1, solve(L, R, midx));
    if (needleft < INF) {
      whole = 1;
      int choices = L.size() - needleft + ((midx != -1) ? 1 : 0);
      final += 1LL * (long long)choices * (long long)(l);
    }
    reverse(a + 1, a + n + 1);
  }
  if (whole) {
    final += 1LL * (long long)(l) * (long long)(l);
  }
  printf("%lld\n", final);
}

### Prompt

Please create a solution in CPP 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 long UNDEF = -1;
const long long INF = 1e9;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int readInt() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
const int mn = 1e5 + 2;
int a[mn];
vector<int> getodd(vector<int> &L, vector<int> &R) {
  map<int, int> h;
  for (auto &w : L) h[w]++;
  for (auto &w : R) h[w]++;
  vector<int> vodd;
  for (auto &w : h)
    if (w.second % 2 != 0) vodd.push_back(w.first);
  return vodd;
}
int help(vector<int> &L, vector<int> &R) {
  int lsz = L.size();
  assert(lsz == R.size());
  map<int, int> h;
  for (auto &w : L) h[w]++;
  for (auto &w : R) h[w]--;
  int excess = 0;
  for (auto &w : h) {
    if (abs(w.second) % 2 != 0) return INF;
    if (w.second > 0) excess += w.second;
  }
  if (excess <= 0) {
    return 0;
  }
  for (int i = 0; i < lsz; i++) {
    int x = L[i];
    if (h[x] >= 2) {
      h[x] -= 2;
      excess -= 2;
    }
    if (excess <= 0) {
      return i + 1;
    }
  }
  return INF;
}
int solve(vector<int> &L, vector<int> &R, int mid) {
  int final = help(L, R);
  if (final > 0 && mid != -1) final++;
  int lsz = L.size();
  if (mid != -1) {
    vector<int> vodd = getodd(L, R);
    if (vodd.size() == 2 && (vodd[0] == mid || vodd[1] == mid)) {
      int other = -1;
      for (auto &w : vodd)
        if (w != mid) other = w;
      for (int k = 0; k < 3; k++) {
        vector<int> cL = L, cR = R;
        int minidx = -1;
        if (k == 0) {
          for (int i = 0; i < lsz; i++)
            if (cL[i] == other) {
              cL[i] = mid;
              minidx = i;
              break;
            }
        } else if (k == 1) {
          for (int i = lsz - 1; lsz >= 0; lsz--)
            if (cL[i] == other) {
              cL[i] = mid;
              minidx = i;
              break;
            }
        } else {
          for (auto &w : cR)
            if (w == other) {
              w = mid;
              break;
            }
        }
        chkmin(final, max(minidx + 1, help(cL, cR)) + 1);
      }
    }
  }
  return final;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = readInt();
  for (int i = 1; i <= n; i++) a[i] = readInt();
  int l = -1, r = -1;
  int l2 = -1, r2 = -1;
  for (int i = 1; i <= n; i++) {
    if (i < n + 1 - i) {
      if (a[i] != a[n + 1 - i]) {
        l = i;
        r = n + 1 - i;
        break;
      }
    }
  }
  int ml2;
  for (int i = 1; i <= n; i++) {
    if (i < n + 1 - i) {
      if (a[i] != a[n + 1 - i]) {
        l2 = i;
        r2 = n + 1 - i;
      }
      ml2 = i;
    }
  }
  if (l == -1) {
    printf("%lld\n", ((long long)n * (long long)(n + 1LL)) / 2);
    return 0;
  }
  int whole = 0;
  long long final = 0;
  {
    bool ok = 1;
    map<int, int> h;
    for (int x = l; x <= l2; x++) h[a[x]]++;
    for (int x = r2; x <= r; x++) h[a[x]]--;
    for (auto &w : h)
      if (w.second != 0) ok = 0;
    if (ok) {
      final += 2LL * (ml2 - l2 + 1) * l;
    }
  }
  for (int t = 0; t < 2; t++) {
    vector<int> L, R;
    int midx = -1;
    if (n % 2 == 1) {
      int mid = (n + 1) / 2;
      for (int x = mid - 1; x >= l; x--) L.push_back(a[x]);
      for (int x = mid + 1; x <= r; x++) R.push_back(a[x]);
      midx = a[mid];
    } else {
      for (int x = n / 2; x >= l; x--) L.push_back(a[x]);
      for (int x = (n / 2) + 1; x <= r; x++) R.push_back(a[x]);
    }
    int needleft = max(1, solve(L, R, midx));
    if (needleft < INF) {
      whole = 1;
      int choices = L.size() - needleft + ((midx != -1) ? 1 : 0);
      final += 1LL * (long long)choices * (long long)(l);
    }
    reverse(a + 1, a + n + 1);
  }
  if (whole) {
    final += 1LL * (long long)(l) * (long long)(l);
  }
  printf("%lld\n", final);
}

```