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.