CF1168B.Good Triple

Toad Rash has a binary string $s$. A binary string consists only of zeros and ones.

Let $n$ be the length of $s$.

Rash needs to find the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x \lt x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.

Find this number of pairs for Rash.

蟾蜍拉什有一个二进制字符串 $s$。二进制字符串仅由 0 和 1 组成。

设 $n$ 为 $s$ 的长度。

拉什需要找出满足以下条件的整数对 $l, r$ 的个数：$1 \leq l \leq r \leq n$，且存在一对整数 $x, k$，使得 $1 \leq x, k \leq n$，$l \leq x < x + 2k \leq r$，并且 $s_x = s_{x+k} = s_{x+2k}$。

请帮拉什求出满足条件的整数对个数。

The first line contains the string $s$ ($1 \leq |s| \leq 300\,000$), consisting of zeros and ones.

第一行包含字符串 $s$（$1 \leq |s| \leq 300\,000$），由字符 0 和 1 组成。

Output one integer: the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x \lt x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.

输出一个整数：满足 $1 \leq l \leq r \leq n$ 的整数对 $(l, r)$ 的个数，且存在至少一对整数 $x$、$k$，使得 $1 \leq x, k \leq n$，$l \leq x < x + 2k \leq r$，并且 $s_x = s_{x+k} = s_{x+2k}$。

In the first example, there are three $l$, $r$ pairs we need to count: $1$, $6$; $2$, $6$; and $1$, $5$.

In the second example, there are no values $x$, $k$ for the initial string, so the answer is $0$.

在第一个例子中，我们需要统计三对 $l$、$r$：$1$、$6$；$2$、$6$；以及 $1$、$5$。

在第二个例子中，初始字符串不存在满足条件的 $x$、$k$ 值，因此答案为 $0$。