643. Bear and Strings
The bear has a string s = s1s2... s|s| (where |s| is the length of the string), which consists of lowercase English letters. The bear wants to determine the number of pairs of indices i, j (where 1 ≤ i ≤ j ≤ |s|) such that the substring x(i, j) = sisi+1... sj contains at least one occurrence of the string "bear" as a substring. A substring x(i, j) contains the string "bear" if there exists an index k (where i ≤ k ≤ j - 3) such that sk = b, sk+1 = e, sk+2 = a, and sk+3 + 3 = r. Assist the bear in solving this problem.
The first line contains a non-empty string s (where 1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.
Print a single number, which is the answer to the problem.
1 <= |s| <= 5000