E. Миша и палиндромность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Миши есть массив из 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].

Ваша задача — найти палиндромность Мишиного массива.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 105).

Во второй строке находятся n положительных целых чисел a[i] (1 ≤ a[i] ≤ n), разделённых пробелами — элементы Мишиного массива.

Выходные данные

В единственной строке выведите ответ на задачу.

Примеры
Входные данные
3
2 2 2
Выходные данные
6
Входные данные
6
3 6 5 3 3 5
Выходные данные
0
Входные данные
5
5 5 2 5 2
Выходные данные
4
Примечание

В первом примере подходит любая пара возможная пара (l, r).

В третьем примере подходят пары (1, 3), (1, 4), (1, 5), (2, 5).