none
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*<=≤<=105).

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.