Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of `0` and `1`.

Now, Takahashi will do the operation with the following two steps |T| times.

* Insert a `0` or a `1` at any position of S of his choice.
* Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is `01101`, the digits in the odd positions are `0`, `1`, `1` from left to right, so x is incremented by 2.



Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

* 1 \leq |T| \leq 2 \times 10^5
* T consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


T


Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Examples

Input

1101


Output

5


Input

0111101101


Output

26
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    string t;
    cin >> t;
    ll ans = 0, cnt = 0;
    bool one = true;
    for (auto &c:t) {
        if (c == '1' || !one) {
            if (one) 
                cnt++;
            if (c == '0') 
                c = '-';
            ans += cnt;
            one ^= 1;
        }
    }
    reverse(t.begin(), t.end());
    one ^= 1;
    ll sum = 0, odds = 0;
    for (auto &c:t) {
        if (c == '0') {
            cnt -= odds;
            odds = sum - odds;
            cnt += odds;
            ans += cnt;
        } else {
            if (c == '1') {
                if (one) odds++;
                sum++;
            }
            one ^= 1;
        }
    }
    cout << ans << '\n';
    return 0;
}