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 <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int n,k; char T[maxn];
vector<int> a[maxn];
namespace seg {
	const int maxnode=maxn<<2;
	int sum[maxnode][2];
	bool rev[maxnode];
	inline void rever(int u) {
		rev[u]^=1;
		swap(sum[u][0],sum[u][1]);
	}
	inline void pushdown(int u) {
		if(rev[u]) {
			rever(u<<1);
			rever(u<<1|1);
			rev[u]=0;
		}
	}
	inline void pushup(int u) {
		sum[u][0]=sum[u<<1][0]+sum[u<<1|1][0];
		sum[u][1]=sum[u<<1][1]+sum[u<<1|1][1]; 
	}
	void build(int u,int l,int r) {
		if(l==r) {
			sum[u][l&1]=T[l]-'0';
			return;
		}
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
	void update(int u,int l,int r,int qp) {
		if(l==r) {
			sum[u][0]=sum[u][1]=0;
			return;
		}
		pushdown(u);
		int mid=(l+r)>>1;
		if(qp<=mid) update(u<<1,l,mid,qp);
		else update(u<<1|1,mid+1,r,qp);
		pushup(u);
	}
	void update(int u,int l,int r,int ql,int qr) {
		if(l==ql&&r==qr) {
			rever(u);
			return;
		}
		pushdown(u);
		int mid=(l+r)>>1;
		if(qr<=mid) update(u<<1,l,mid,ql,qr);
		else if(ql>mid) update(u<<1|1,mid+1,r,ql,qr);
		else {
			update(u<<1,l,mid,ql,mid);
			update(u<<1|1,mid+1,r,mid+1,qr);
		}
		pushup(u);
	}
}
int main() {
	scanf("%s",T+1),n=strlen(T+1);
	for(int i=1;i<=n;++i) {
		if(T[i]=='0') a[k].push_back(i);
		else {
			if(T[i+1]=='1') {++i; continue;}
			++k;
		}
	}
	if(a[k].size()) ++k;
	vector<int> ord;
	for(int i=0;i<k;++i) {
		for(int j=bool(i);j<a[i].size();++j) ord.push_back(a[i][j]);
	}
	for(int i=k-1;i>0;--i) {
		ord.push_back(a[i][0]);
	}
	for(int i=1;i<=n;++i) if(T[i]=='1') ord.push_back(i);
	seg::build(1,1,n);
	ll an=0;
	for(int i=0;i<ord.size();++i) {
		int x=ord[i];
		an+=seg::sum[1][1];
		seg::update(1,1,n,x);
		seg::update(1,1,n,x,n);
	}
	printf("%lld\n",an);
	return 0;
}