Bộ Ba Tốt

Cho một xâu nhị phân $s$ (chỉ gồm các ký tự $0$ và $1$) có độ dài $n$.

Gọi một cặp chỉ số $(l,r)$ với $1\le l\le r\le n$ là tốt nếu tồn tại một cấp số cộng gồm ba vị trí nằm hoàn toàn trong đoạn $[l,r]$ có giá trị bằng nhau. Cụ thể, tồn tại hai số nguyên $x,k$ với $k\ge 1$ sao cho:

$$l\le x<x+k<x+2k\le r\text{và}{s}_x=s_{x+k}=s_{x+2k}.$$

Hãy đếm số cặp $(l,r)$ tốt.

Dữ liệu vào

• Một dòng duy nhất chứa xâu nhị phân $s$.

Dữ liệu ra

• Một số nguyên: số cặp $(l,r)$ tốt.

Ràng buộc

• $1\le |s|\le 3·{10}^5$
• $s$ chỉ gồm các ký tự $0$ và $1$.

Ví dụ