CF501E Misha and Palindrome Degree

Misha 有一个长度为 $n$ 的整数数组，数组下标从 $1$ 到 $n$。我们将数组 $a$ 的“回文度”定义为满足如下条件的下标对 $(l, r)$ 的数量：$1 \leq l \leq r \leq n$，使得将第 $l$ 个到第 $r$ 个（包含 $l$ 和 $r$）的数重新排列后，整个数组都可以变成回文数组。换句话说，$(l, r)$ 这一对需要满足：只要你对 $l$ 到 $r$ 这段区间随意排列（也可以什么都不做），对于任意 $1 \leq i \leq n$，始终有 $a[i] = a[n - i + 1]$。 你的任务是计算 Misha 数组的回文度。

第一行输入一个整数 $n$，表示数组的长度（$1 \leq n \leq 10^{5}$）。 第二行输入 $n$ 个正整数 $a[i]$ （$1 \leq a[i] \leq n$），用空格分隔，表示 Misha 的数组元素。

输出一个整数，表示答案。

在第一个样例中，所有可能的 $(l, r)$ 都满足条件。 在第三个样例中，满足条件的对 $(l, r)$ 为 $(1,3)$、$(1,4)$、$(1,5)$ 和 $(2,5)$。 由 ChatGPT 5 翻译