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⁵).

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.