Good Triple

题意翻译

给出01串s，求数对[l,r]个数，使得能找到至少一对[x,k],使1<=x,k<=|s|且l<=x<x+2k<=r且s[x]=s[x+k]=s[x+2k]

题目描述

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 < x + 2k \leq r $ , and $ s_x = s_{x+k} = s_{x+2k} $ . Find this number of pairs for Rash.

输入输出格式

输入格式

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

输出格式

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 < x + 2k \leq r $ , and $ s_x = s_{x+k} = s_{x+2k} $ .

输入输出样例

输入样例 #1

010101

输出样例 #1

3

输入样例 #2

11001100

输出样例 #2

0

说明

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 $ .

题意翻译

给出01串s，求数对[l,r]个数，使得能找到至少一对[x,k],使1<=x,k<=|s|且l<=x<x+2k<=r且s[x]=s[x+k]=s[x+2k]