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 "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
string A;
ll n,ans;
int main(){
	FAST
	cin>>A;
	n=A.size();
	ll zero=count(all(A),'0');
	vector<char> v(n,'*');
	ll pos=0;
	FOR(i,0,n-1){
		if(A[i]=='0'){
			v[pos++]=A[i];
		}else{
			if(pos > 0 && v[pos-1] == A[i]){
				-- pos;
				ans += zero;
			}else{
				v[pos++]=A[i];
			}
		}
	}
	ll sofar=0;
	FOR(i,0,pos-1)if(v[i]=='1'){
		auto getOdd=[&](ll l,ll r){
			if(l%2==0) ++ l;
			if(r%2==0) -- r;
			return l>r ? 0 : (r-l+2)/2;
		};
		++ sofar;
		ans += zero - getOdd(sofar, i);
	}
	ll one=count(all(A),'1');
	FOR(i,1,one){
		ans+=(i+1)/2;
	}
	cout<<ans<<'\n';
}
