题目描述

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$ 的回文度数。

输入格式

第一行一个整数 $n$，$1\le n\le 10^{5}$。

第二行 $n$ 个整数 $a_i$，$1 \le a_i \le n$。

输出格式

一行一个整数表示答案。

3
2 2 2

6

6
3 6 5 3 3 5

0

5
5 5 2 5 2

4