Misha 有一个由 n 个整数组成的数组,索引为 1 到 n 的整数。我们将数组 a 的回文度定义为这样的索引对 (l, r)(1 ≤ l ≤ r ≤ n) 的数量,即从第 l 到第 r 个元素可以重新排列,使整个数组成为回文。换句话说,对 (l, r) 应该满足这样的条件:在对从 l 到 r 的位置上的数字进行一些重新排列(允许完全不重新排列数字)之后,对于任何 1 ≤ i ≤ n,以下条件成立:a[i] = a[n - i + 1]。
你的任务是找到 Misha 数组的回文度。
输入
第一行包含整数 n (1 ≤ n ≤ 105)。
第二行包含 n 个正整数 a[i] (1 ≤ a[i] ≤ n),用空格分隔 — Misha 数组的元素。
输出
在一行中打印问题的答案。
示例
输入 #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
注意
在第一个样本测试中,任何可能的对 (l, r) 都满足条件。
在第三个样本测试中,以下对 (1, 3)、(1, 4)、(1, 5)、(2, 5) 满足条件。