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\ninput = sys.stdin.readline\n\nS=input().strip()\nL=len(S)\n\nANS1=[0]*(L+10)\nANS2=[0]*(L+10)\nANS3=[0]*(L+10)\n\nfor i in range(L-2):\n    if S[i]==S[i+1]==S[i+2]:\n        ANS1[i]=1\n\nfor i in range(L-4):\n    if S[i]==S[i+2]==S[i+4]:\n        ANS2[i]=1\n\nfor i in range(L-6):\n    if S[i]==S[i+3]==S[i+6]:\n        ANS3[i]=1\n\nSCORE=0\n\nfor i in range(L):\n    if ANS1[i]==1:\n        SCORE+=max(0,L-i-2)\n    elif ANS1[i+1]==1:\n        SCORE+=max(0,L-i-3)\n    elif ANS1[i+2]==1:\n        SCORE+=max(0,L-i-4)\n\n    elif ANS2[i]==1:\n        SCORE+=max(0,L-i-4)\n    elif ANS2[i+1]==1:\n        SCORE+=max(0,L-i-5)\n\n        \n    elif ANS1[i+3]==1:\n        SCORE+=max(0,L-i-5)\n\n\n        \n        \n    elif ANS1[i+4]==1:\n        SCORE+=max(0,L-i-6)\n    elif ANS2[i+2]==1:\n        SCORE+=max(0,L-i-6)\n    elif ANS3[i]==1:\n        SCORE+=max(0,L-i-6)\n        \n    elif ANS1[i+5]==1:\n        SCORE+=max(0,L-i-7)\n    elif ANS2[i+3]==1:\n        SCORE+=max(0,L-i-7)\n    elif ANS3[i+1]==1:\n        SCORE+=max(0,L-i-7)\n     \n\n    else:\n        SCORE+=max(0,L-i-8)\n\n    #print(SCORE)\n\nprint(SCORE)\n        \n        \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14321