У Миши есть массив из 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].
Ваша задача — найти палиндромность Мишиного массива.
Выходные данные
В единственной строке выведите ответ на задачу.
Примечание
В первом примере подходит любая пара возможная пара (l, r).
В третьем примере подходят пары (1, 3), (1, 4), (1, 5), (2, 5).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2 2
|
6
|
|
2
|
6
3 6 5 3 3 5
|
0
|
|
3
|
5
5 5 2 5 2
|
4
|