A pareidolia é o fenómeno em que os olhos tendem a ver padrões familiares em imagens onde estes não existem realmente, por exemplo, ver um rosto numa nuvem. Como pode imaginar, devido à sua constante proximidade às vacas, Farmer John vê frequentemente padrões relacionados com vacas em objetos do dia a dia. Por exemplo, ao olhar para a cadeia "bqessiyexbesszieb", os seus olhos ignoram algumas letras e ele vê apenas "bessiebessie".
Dada uma cadeia $s$, seja $B(s)$ o número máximo de cópias repetidas de "bessie" que se podem formar eliminando zero ou mais caracteres de $s$. No exemplo acima, $B(\texttt{bqessiyexbesszieb}) = 2$.
Calcular $B(s)$ é um desafio interessante, mas Farmer John quer resolver um desafio ainda mais interessante: dada uma cadeia $t$ de comprimento no máximo $3\cdot 10^5$, composta apenas pelos caracteres a-z, calcule a soma de $B(s)$ sobre todas as subcadeias contíguas $s$ de $t$.
Entrada
A entrada consiste numa cadeia não vazia de comprimento no máximo $3\cdot 10^5$, cujos caracteres são todos letras minúsculas inglesas.
Saída
Imprima um único número: o número total de cópias de "bessie" que podem ser formadas em todas as subcadeias da cadeia de entrada.
Exemplos
Entrada 1
bessiebessie
Saída 1
14
Nota
Doze subcadeias contêm exatamente 1 "bessie", e 1 cadeia contém exatamente 2 cópias de "bessie", pelo que o total é $12\cdot 1 + 1 \cdot 2 = 14$.
Entrada 2
abcdefghssijebessie
Saída 2
28
Subtarefas
- Entradas 3-5: a cadeia tem comprimento no máximo $5000$.
- Entradas 6-12: sem restrições adicionais.
Autores do problema: Brandon Wang e Benjamin Qi