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

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