Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string s_1s_2… s_n of length n. 1 represents an apple and 0 represents an orange.

Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let f(l,r) be the longest contiguous sequence of apples in the substring s_{l}s_{l+1}… s_{r}. 

Help Zookeeper find ∑_{l=1}^{n} ∑_{r=l}^{n} f(l,r), or the sum of f across all substrings.

Input

The first line contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The next line contains a binary string s of length n (s_i ∈ \{0,1\}) 

Output

Print a single integer: ∑_{l=1}^{n} ∑_{r=l}^{n} f(l,r). 

Examples

Input


4
0110


Output


12


Input


7
1101001


Output


30


Input


12
011100011100


Output


156

Note

In the first test, there are ten substrings. The list of them (we let [l,r] be the substring s_l s_{l+1} … s_r):

  * [1,1]: 0 
  * [1,2]: 01 
  * [1,3]: 011 
  * [1,4]: 0110 
  * [2,2]: 1 
  * [2,3]: 11 
  * [2,4]: 110 
  * [3,3]: 1 
  * [3,4]: 10 
  * [4,4]: 0 



The lengths of the longest contiguous sequence of ones in each of these ten substrings are 0,1,2,2,1,2,2,1,1,0 respectively. Hence, the answer is 0+1+2+2+1+2+2+1+1+0 = 12.
#include <bits/stdc++.h>
namespace FastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
inline bool read(T& x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return false;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
  return true;
}
template <class T, class... U>
bool read(T& h, U&... t) {
  return read(h) && read(t...);
}
};  // namespace FastIO
using namespace std;
using namespace FastIO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long INF = 0x3f3f3f3f;
const long long N = 5e5 + 10;
struct node {
  long long l, r, mid, len, ma, sum, lazyma, lazysum;
} tree[N << 2];
void pp(long long x) {
  tree[x].ma = max(tree[x << 1].ma, tree[x << 1 | 1].ma);
  tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
}
void build(long long x, long long l, long long r) {
  tree[x] = {l, r, l + r >> 1, r - l + 1, 0, 0, 0, 0};
  if (l == r) return;
  long long mid = tree[x].mid;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
void pd(long long x) {
  if (tree[x].lazyma) {
    long long ma = tree[x].lazyma;
    tree[x].lazysum = tree[x << 1].lazysum = tree[x << 1 | 1].lazysum = 0;
    tree[x << 1].lazyma = tree[x << 1 | 1].lazyma = ma;
    tree[x << 1].ma = tree[x << 1 | 1].ma = ma;
    tree[x << 1].sum = tree[x << 1].len * ma;
    tree[x << 1 | 1].sum = tree[x << 1 | 1].len * ma;
  }
  if (tree[x].lazysum) {
    long long sum = tree[x].lazysum;
    tree[x << 1].lazysum += sum;
    tree[x << 1 | 1].lazysum += sum;
    if (tree[x << 1].lazyma) tree[x << 1].lazyma += sum;
    if (tree[x << 1 | 1].lazyma) tree[x << 1 | 1].lazyma += sum;
    tree[x << 1].ma += sum;
    tree[x << 1 | 1].ma += sum;
    tree[x << 1].sum += tree[x << 1].len * sum;
    tree[x << 1 | 1].sum += tree[x << 1 | 1].len * sum;
  }
  tree[x].lazyma = tree[x].lazysum = 0;
}
void modify_add(long long x, long long l, long long r, long long k) {
  if (l <= tree[x].l && tree[x].r <= r) {
    tree[x].ma += k;
    tree[x].sum += tree[x].len * k;
    tree[x].lazysum += k;
    if (tree[x].lazyma) tree[x].lazyma += k;
    return;
  }
  pd(x);
  long long mid = tree[x].mid;
  if (l <= mid) modify_add(x << 1, l, r, k);
  if (r > mid) modify_add(x << 1 | 1, l, r, k);
  pp(x);
}
void modify_max(long long x, long long l, long long r, long long k) {
  if (l <= tree[x].l && tree[x].r <= r) {
    tree[x].ma = k;
    tree[x].sum = k * tree[x].len;
    tree[x].lazyma = k;
    tree[x].lazysum = 0;
    return;
  }
  pd(x);
  long long mid = tree[x].mid;
  if (l <= mid) modify_max(x << 1, l, r, k);
  if (r > mid) modify_max(x << 1 | 1, l, r, k);
  pp(x);
}
pair<long long, long long> query(long long x, long long k) {
  if (tree[x].len == 1) return make_pair(tree[x].l, tree[x].ma);
  pd(x);
  if (tree[x << 1 | 1].ma > k)
    return query(x << 1 | 1, k);
  else
    return query(x << 1, k);
  pp(x);
}
char s[N];
signed main() {
  long long n;
  cin >> n;
  cin >> s + 1;
  long long last = 0;
  long long ans = 0;
  build(1, 1, n);
  for (long long i = 1; i <= n; i++) {
    if (s[i] == '1') {
      if (!last) last = i;
      modify_add(1, last, i, 1);
      long long len = i - last + 1;
      auto x = query(1, len);
      long long pos = x.first;
      long long val = x.second;
      if (pos < last - 1 && val > len)
        modify_max(1, pos + 1, last - 1, len);
      else
        modify_max(1, 1, last, len);
    } else {
      last = 0;
    }
    ans += tree[1].sum;
  }
  cout << ans << endl;
  return 0;
}
