Toad Rash 有一个二进制字符串 $$$s$$$。二进制字符串仅由零和一组成。
令 $$$n$$$ 为 $$$s$$$ 的长度。
Rash 需要找到这样的整数对 $$$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}$$$。
找出 Rash 的配对数。
输入
第一行包含字符串 $$$s$$$ ($$$1 \leq |s| \leq 300\,000$$$),由零和一组成。
输出
输出一个整数:$$$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}$$$。
示例
输入 #1
010101
输出 #1
3
输入 #2
11001100
输出 #2
0
注意
在第一个示例中,我们需要计算三个 $$$l$$$、$$$r$$$ 对:$$$1$$$、$$$6$$$; $$$2$$$、$$$6$$$;和$$$1$$$、$$$5$$$。
在第二个示例中,初始字符串没有值 $$$x$$$、$$$k$$$,因此答案为 $$$0$$$。