CF501E.Misha and Palindrome Degree

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.

米沙有一个长度为 $n$ 的整数数组，数组下标从 $1$ 到 $n$。我们定义数组 $a$ 的回文度为满足如下条件的下标对 $(l,\,r)$（其中 $1 \leq l \leq r \leq n$）的个数：将第 $l$ 个到第 $r$ 个（含端点）元素重新排列后，整个数组 $a$ 成为一个回文数组。换言之，下标对 $(l,\,r)$ 需满足：在对位置 $l$ 到 $r$（含端点）上的数进行某种重排（允许不作任何重排）后，对任意 $1 \leq i \leq n$，均有

$$a[i] = a[n - i + 1].$$

你的任务是求出米沙的数组的回文度。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。

第二行包含 $n$ 个正整数 $a[i]$（$1 \leq a[i] \leq n$），以空格分隔——即米沙数组的元素。

In a single line print the answer to the problem.

在一行中输出问题的答案。

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.

在第一个样例测试中，任意可能的数对 $(l, r)$ 均满足条件。

在第三个样例测试中，以下数对 $(1, 3), (1, 4), (1, 5), (2, 5)$ 满足条件。