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.


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
010101

Output
3

Input
11001100

Output
0



-----Note-----

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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nfrom collections import deque\n#from functools import *\n#from fractions import Fraction as f\n#from copy import *\n#from bisect import *\t\n#from heapq import *\n#from math import gcd,ceil,sqrt\n#from itertools import permutations as prm,product\n \ndef eprint(*args):\n    print(*args, file=sys.stderr)\nzz=1\n \n#sys.setrecursionlimit(10**6)\nif zz:\n\tinput=sys.stdin.readline\nelse:\t\n\tsys.stdin=open(\'input.txt\', \'r\')\n\tsys.stdout=open(\'all.txt\',\'w\')\ndi=[[-1,0],[1,0],[0,1],[0,-1]]\n\ndef string(s):\n\treturn "".join(s)\ndef fori(n):\n\treturn [fi() for i in range(n)]\t\ndef inc(d,c,x=1):\n\td[c]=d[c]+x if c in d else x\ndef bo(i):\n\treturn ord(i)-ord(\'A\')\t\ndef li():\n\treturn [int(xx) for xx in input().split()]\ndef fli():\n\treturn [float(x) for x in input().split()]\t\ndef comp(a,b):\n\tif(a>b):\n\t\treturn 2\n\treturn 2 if a==b else 0\t\t\ndef gi():\t\n\treturn [xx for xx in input().split()]\ndef cil(n,m):\n\treturn n//m+int(n%m>0)\t\ndef fi():\n\treturn int(input())\ndef pro(a): \n\treturn reduce(lambda a,b:a*b,a)\t\t\ndef swap(a,i,j): \n\ta[i],a[j]=a[j],a[i]\t\ndef si():\n\treturn list(input().rstrip())\t\ndef mi():\n\treturn \tmap(int,input().split())\t\t\t\ndef gh():\n\tsys.stdout.flush()\ndef isvalid(i,j):\n\treturn 0<=i<n and 0<=j<m and a[i][j]!="."\ndef bo(i):\n\treturn ord(i)-ord(\'a\')\t\ndef graph(n,m):\n\tfor i in range(m):\n\t\tx,y=mi()\n\t\ta[x].append(y)\n\t\ta[y].append(x)\n\n\nt=1\n\n\nwhile t>0:\n\tt-=1\n\ts=si()\n\tn=len(s)\n\tp=[n]*(n+1)\n\tans=0\n\tfor i in range(n):\n\t\tk=1\n\t\twhile i+2*k<n:\n\t\t\tif s[i]==s[i+k]==s[i+2*k]:\n\t\t\t\tp[i]=i+2*k\n\t\t\t\tbreak\n\t\t\tk+=1\n\tfor i in range(n-2,-1,-1):\n\t\tp[i]=min(p[i],p[i+1])\n\t\tans+=(n-p[i])\n\tprint(ans)\t\t\n\n\t\t\t\n\t\t\t\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17429