Zadanie

Dobré substringy

Počet bodov: 20, časový limit: 300ms

Substring je dobrý, ak obsahuje aspoň jednu \(1\). Koľko je v stringu \(s\) dobrých substringov?

Vstup a výstup

Na jedinom riadku vstupu dostanete reťazec \(s\) postavený zo znakov \(0\) a \(1\).

Na jediný riadok výstupu vypíšte, koľko súvislých podúsekov reťazca \(s\) v sebe obsahuje aspoň jeden znak \(1\).

Hodnotenie

Platí, že \(1 \leq n \leq 200\,000\). Sú 4 sady vstupov. V prvej navyše platí, že \(n \leq 300\) a v druhej platí, že \(n \leq 5\,000\).

Príklad

Input:

0101

Output:

8