B. Best Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a binary string $$$S$$$. You can perform the following operation any number of times:

  • Replace one substring '0101' with '1010'.
What is the maximum number of operations you can perform?
Input

A binary string $$$S$$$ ($$$1\leq |S| \leq 5\times 10^6$$$).

Output

One integer — the answer.

Examples
Input
10100010011001011111
Output
5
Input
0000010101100110101101010110000110100\
1110000100101111111001011011101010001\
11101111010101010010101010
(There won’t be extra line breakers \
in the actual test cases.)
Output
58