302596: CF501E. Misha and Palindrome Degree
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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.
输入输出样例
输入样例 #1
3
2 2 2
输出样例 #1
6
输入样例 #2
6
3 6 5 3 3 5
输出样例 #2
0
输入样例 #3
5
5 5 2 5 2
输出样例 #3
4