Pareidolia

Time limit4sMemory limit1024 MB

Summary

Given a lowercase string of up to 300000 characters, sum B(s) over all substrings s, where B(s) is how many copies of "bessie" can be picked as subsequences of s.

Level: Medium7 of 10
Topics: Dynamic programming, String matching, Two pointers
Solved: No attempts yet

Problem

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist, for example seeing a face in a cloud. Farmer John is constantly near cows, so he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", his eyes ignore some of the letters and all he sees is "bessiebessie".

Given a string $s$ , let $B(s)$ be the maximum number of repeated copies of "bessie" that can be formed by deleting zero or more characters from $s$ . In the example above, $B("bqessiyexbesszieb") = 2$ .

Farmer John wants to solve an even more interesting challenge. Given a string $t$ of length at most $3\cdot 10^5$ consisting only of lowercase letters a-z, compute the sum of $B(s)$ over all contiguous substrings $s$ of $t$ .

Input

The input consists of a nonempty string of length at most $3\cdot 10^5$ whose characters are all lowercase English letters.

Output

Output a single number, the total number of bessies that can be made across all substrings of the input string.

Examples2

Example 1
Input
```
bessiebessie
```
Expected output
```
14
```
Example 2
Input
```
abcdefghssijebessie
```
Expected output
```
28
```