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<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

int main(){
    string t;
    cin>>t;
    int n = t.size();
    vector<int> used(n);
    ll ans = 0;
    int sum = 0;
    int len = 0;
    for(int i=0;i<n;i++){
        if(len%2==1 || t[i]=='1'){
            used[i] = true;
            if(len%2==0 && t[i]=='1') sum++;
            ans += sum;
            len++;
        }
    }
    cerr<<ans<<endl;
    int even_one = 0;
    int odd_one = 0;
    for(int i=n-1;i>=0;i--){
        if(used[i]){
            if(t[i]=='1'){
                if(len%2==1){
                    odd_one++;
                    sum--;
                }
                else even_one++;
            }
            len--;
        }
        else{
            swap(even_one,odd_one);
            // cerr<<sum+odd_one<<endl;
            ans+=sum+odd_one;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}
