H. Упоротые палиндромы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Ваша задача состоит в том, чтобы поддерживать очередь содержащую строчные буквы Латинского алфавита со следующими операциями:

  • «push $$$c$$$»: вставить букву $$$c$$$ в конец очереди;
  • «pop»: удалить букву из начала очереди.

Изначально очередь пустая.

После каждой операции, вы должны посчитать число различных подстрок палиндромов в строке, которая получается соединением букв от начала к концу очереди.

Число различных подстрок палиндромов пустой строки равняется $$$0$$$.

Строка $$$s[1..n]$$$ длины $$$n$$$ является палиндромом, если $$$s[i] = s[n-i+1]$$$ для любого $$$1 \leq i \leq n$$$.

Строка $$$s[l..r]$$$ является подстрокой строки $$$s[1..n]$$$ для любого $$$1 \leq l \leq r \leq n$$$.

Две строки $$$s[1..n]$$$ и $$$t[1..m]$$$ различные, если выполняется как минимум одно из условий.

  • $$$n \neq m$$$;
  • $$$s[i] \neq t[i]$$$ для некоторого $$$1 \leq i \leq \min\{n,m\}$$$.
Входные данные

В первой строке содержится целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$), означающее число операций.

Далее следуют $$$q$$$ строк. Каждая строка содержит одну из операций.

  • «push $$$c$$$»: вставить $$$c$$$ в конец очереди, где $$$c$$$ это строчная буква Латинского алфавита;
  • «pop»: удалить букву из начала очереди.

Гарантируется, что операция «pop» не будет применяться к пустой очереди.

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

После каждой операции, выведите количество различных подстрок палиндромов в строке, представленной в очереди.

Пример
Входные данные
12
push a
pop
push a
push a
push b
push b
push a
push a
pop
pop
pop
push b
Выходные данные
1
0
1
2
3
4
5
6
5
4
3
4
Примечание

Пусть $$$s_k$$$ это строка находящаяся в очереди после $$$k$$$-й операции, и пусть $$$c_k$$$ будет число различных подстрок палиндромов строки $$$s_k$$$. Следующая таблица иллюстрирует пример.

$$$k$$$$$$s_k$$$$$$c_k$$$
$$$1$$$$$$a$$$$$$1$$$
$$$2$$$$$$\textsf{empty}$$$$$$0$$$
$$$3$$$$$$a$$$$$$1$$$
$$$4$$$$$$aa$$$$$$2$$$
$$$5$$$$$$aab$$$$$$3$$$
$$$6$$$$$$aabb$$$$$$4$$$
$$$7$$$$$$aabba$$$$$$5$$$
$$$8$$$$$$aabbaa$$$$$$6$$$
$$$9$$$$$$abbaa$$$$$$5$$$
$$$10$$$$$$bbaa$$$$$$4$$$
$$$11$$$$$$baa$$$$$$3$$$
$$$12$$$$$$baab$$$$$$4$$$

Стоит заметить, что

  • После $$$2$$$-й операции, строка пустая и у нее нет подстрок. Значит ответ $$$0$$$;
  • После $$$8$$$-й операции, строка «$$$aabbaa$$$». У нее $$$6$$$ различных подстрок палиндромов «$$$a$$$», «$$$aa$$$», «$$$aabbaa$$$», «$$$abba$$$», «$$$b$$$», and «$$$bb$$$».