A9684. 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.

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.

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.