Misha and Palindrome Degree

Misha 有一个数组，下标从 $1$ 到 $n$。 定义一个数组 $a$ 的回文度数为数对 $[l,r]$ 的个数（$1 \le l \le r \le n$），当且仅当重排 $[l,r]$ 中的数可以使 $a$ 变成一个回文序列。 换句话说，重排 $[l,r]$ 中的数可以使每个 $i \in [1,n],\,a_i=a_{n-i+1}$。 给出数组 $a$，请你求出 $a$ 的回文度数。

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.

The first line contains integer $ n $ ( $ 1<=n<=10^{5} $ ). The second line contains $ n $ positive integers $ a[i] $ ( $ 1<=a[i]<=n $ ), separated by spaces — the elements of Misha's array.

In a single line print the answer to the problem.

3
2 2 2

6

6
3 6 5 3 3 5

0

5
5 5 2 5 2

4

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.