Строка называется хорошей, если после объединения всех последовательных равных символов в один символ получившаяся строка является палиндромом. Например, «aabba» является хорошей, потому что после объединения одинаковых символов она станет строкой «aba».
Вам дана строка, посчитайте две величины:
- количество хороших ее подстрок четной длины;
- количество хороших ее подстрок нечетной длины.
Примечание
В первом примере есть три хороших подстроки («b», «b», и «bb»). Длина одной из них — четная, длина двух других — нечетная.
Во втором примере есть шесть хороших подстрок («b», «a», «a», «b», «aa», «baab»). Две из них имеют четную длину, остальные четыре — нечетную длину.
В третьем примере есть семь хороших подстрок («b», «a», «b», «b», «bb», «bab», «babb»). Две из них имеют четную длину, остальные пять — нечетную длину.
Определения
Подстрока s[l, r] (1 ≤ l ≤ r ≤ n) строки s = s1s2... sn — это строка slsl + 1... sr.
Строка s = s1s2... sn является палиндромом, если она равна строке snsn - 1... s1.