\(N\) (\(1 \le N \le 7500\)) коров Фермера Джона выстроились в ряд для фотографирования.
Коровы хотят, чтобы ФД сделал \(\frac{N(N+1)}{2}\) групповых фоток по одной для
каждой непрерывной подпоследовательности коров.
Однако ФД имеет свои соображения как выстроить коров. В частности, он
отказывается делать фотку подпоследовательности коров, если она не формирует
палиндром, это означает, что порода \(i\)-ой коровы от левого конца фотки
должна совпадать с породой \(i\)-ой коровы от начала фотки, для всех положительных \(i\)
меньше либо равных длины подпоследовательности.
Каждая корова имеет породу Guernsey или Holstein.
Для каждой из \(\frac{N(N+1)}{2}\) непрерывных подпоследовательностей построения
посчитайте минимальное количество транспозиций, с помощью которых можно реорганизовать
эту подпоследовательность в палиндром или \(-1\), если это сделать невозможно.
Одна транспозиция заключается во взятии двух соседних коров подпоследовательности
и обмене их. Вывод - сумма всех таких количеств.
Заметим, что количество транспозиций необходимо вычислить независимо для каждой
непрерывной подпоследовательности (коровы возвращаются на начальные позиции между фотками).
Формт ввода (с клавиатуры / stdin):
Ряд представленный из символов G и H длины \(N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Сумма вышеописанных количеств по всем \(\frac{N(N+1)}{2}\) непрерывным подпоследовательностям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
GHHGGHHGH
|
12
|