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;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

const int N = 200000;
bitset<N> v, odd, pref;
ll X = 0;

void inc() {
  X += (v & odd).count();
}

const int DEBUG = 0;

ll stupid(string s) {
  int n = s.size();
  vi ord(n);
  for (int i = 0; i < n; ++i) ord[i] = i;
  int ma = 0;
  do {
    vi used(n);
    int sum = 0;
    for (int x : ord) {
      used[x] = 1;
      int c = 0, l = 0;
      for (int i = 0; i < n; ++i) if (used[i]) {
        ++l;
        if (l % 2 && s[i] == '1') ++c;
      }
      sum += c;
    }
    ma = max(ma, sum);
  } while (next_permutation(ord.begin(), ord.end()));
  return ma;
}

void solve(string s) {
  X = 0;
  int n = s.size();
  int c = 0;
  vi used(n);
  for (int i = 0; i < n; ++i) if (s[i] == '1') {
    ++c;
    used[i] = 1;
  }
  int cur = 0;
  for (int i = 0; i < c; ++i) {
    v[i] = 1;
    if (i % 2 == 0) ++cur;
    X += cur;
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      if (p % 2) {
        used[i] = 1;
        ++c;
        if (c % 2) ++cur;
        X += cur;
        ++p;
      }
    } else {
      ++p;
    }
  }
  vi x(2);
  int l = 0;
  for (int i = n - 1; i >= 0; --i) {
    if (!used[i]) {
      vi nx = x;
      swap(nx[0], nx[1]);
      cur += nx[0] - x[0];
      x = nx;
      X += cur;
      ++c;
      ++l;
    } else {
      int j = c - l - 1;
      if (s[i] == '1') x[j % 2]++;
      ++l;
    }
  }
/*  for (int i = 0; i < n; i += 2) odd[i] = 1;
  for (int i = 0; i < c; ++i) {
    pref[i] = v[i] = 1;
    inc();
  }
  int pc = c;
  for (int i = n - 1; i >= 0; --i) if (s[i] == '0') {
    int l = n - i - 1;
    while (pc > c - l) {
      --pc;
      pref[pc] = 0;
    }
    auto prefv = v & pref;
    v = prefv | ((v ^ prefv) << 1);
    ++c;
    inc();
  }*/
  cout << X << endl;
  if (DEBUG) {
    ll res = stupid(s);
    if (res != X) {
      cerr << s << ' ' << res << ' ' << X << endl;
      assert(0);
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  string s(N, '0');
  if (!DEBUG) {
    cin >> s;
    solve(s);
  } else {
    for (int n = 1; n <= 10; ++n) {
      s.resize(n);
      for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
          if (mask & (1 << i)) s[i] = '1';
          else s[i] = '0';
        }
        solve(s);
      }
    }
  }
  return 0;
}
