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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.SplittableRandom;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF1 solver = new TaskF1();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF1 {
        int n;
        char[] s;
        int[] blockSize;
        int[] blockStart;
        int[] blockEnd;
        RMQ blockSizeRMQ;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            in.nextInt();
            s = in.next().toCharArray();

//        boolean stress = true;
            boolean stress = false;
            if (stress) {
                SplittableRandom random = new SplittableRandom(0);
                for (int test = 0; test < 100; test++) {
                    s = new char[100];
//                s = new char[300000];
                    for (int i = 0; i < s.length; i++) {
                        s[i] = (char) ('0' + random.nextInt(2));
                    }
                }
                long u = fast(s.clone());
                long v = slow(s.clone());
//            long v = 0;
                if (u != v) {
                    throw new AssertionError();
                }
            }

            out.println(fast(s));
        }

        private long fast(char[] s) {
            n = s.length;
            blockSize = new int[n];
            blockStart = new int[n];
            blockEnd = new int[n];
            int k = 0;
            for (int i = 0; i < n; ) {
                int j = i;
                while (j < n && s[i] == s[j]) {
                    ++j;
                }
                if (s[i] == '1') {
                    blockSize[k] = j - i;
                    blockStart[k] = i;
                    blockEnd[k] = j;
                    ++k;
                }
                i = j;
            }
            blockSize = Arrays.copyOf(blockSize, k);
            blockStart = Arrays.copyOf(blockStart, k);
            blockEnd = Arrays.copyOf(blockEnd, k);
            blockSizeRMQ = new RMQ(blockSize);

            long ans = 0;
            for (int i = 0; i < k; i++) {

                long numLeft = calcNumLeftEnds(blockSize[i], i);
                long numRight = calcNumRightEnds(blockSize[i], i);
                ans += numLeft * numRight * blockSize[i];

                for (int pref = 1; pref <= blockSize[i]; pref++) {
                    numLeft = calcNumLeftEnds(pref, i);
                    numRight = 1;
                    ans += numLeft * numRight * pref;
                }

                for (int suff = 1; suff <= blockSize[i]; suff++) {
                    numLeft = 1;
                    numRight = calcNumRightEnds(suff, i);
                    ans += numLeft * numRight * suff;
                }

                long sz = blockSize[i];
                long bothEndsInside = sz * (sz + 1) * (sz + 2) / 6;
                ans += bothEndsInside;
            }

            return ans;
        }

        private long calcNumLeftEnds(int t, int i) {
//        int res = 0;
//        for (int l = 0; l < blockStart[i]; l++) {
//            if (largest(l, blockStart[i]) < t) {
//                ++res;
//            }
//        }
//        return res;

            int l = -1;
            int r = i;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (blockSizeRMQ.getMax(m, i - 1) < t) {
                    r = m;
                } else {
                    l = m;
                }
            }

//        int found = -1;
//        for (int j = i - 1; j >= 0; j--) {
//            if (blockSize[j] >= t) {
//                found = j;
//                break;
//            }
//        }
            int found = l;
            int numLeft = blockStart[i];
            if (found >= 0) {
                numLeft -= blockStart[found] + blockSize[found] - (t - 1);
            }
            return numLeft;
        }

        private long calcNumRightEnds(int t, int i) {
//        int res = 0;
//        for (int r = blockEnd[i] + 1; r <= n; r++) {
//            if (largest(blockEnd[i], r) <= t) {
//                ++res;
//            }
//        }
//        return res;

            int l = i;
            int r = blockSize.length;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (blockSizeRMQ.getMax(i + 1, m) <= t) {
                    l = m;
                } else {
                    r = m;
                }
            }

//        int found = blockSize.length;
//        for (int j = i + 1; j < blockSize.length; j++) {
//            if (blockSize[j] > t) {
//                found = j;
//                break;
//            }
//        }
            int found = r;
            int numRight = n - blockEnd[i];
            if (found < blockSize.length) {
                numRight = (blockStart[found] + t) - blockEnd[i];
            }
            return numRight;
        }

        private long slow(char[] s) {
            long res = 0;
            for (int i = 0; i < s.length; i++) {
                int max = 0;
                int cur = 0;
                for (int j = i; j < s.length; j++) {
                    if (s[j] == '0') {
                        cur = 0;
                    } else {
                        cur++;
                        max = Math.max(max, cur);
                    }
                    res += max;
                }
            }
            return res;
        }

        private class RMQ {
            int[][] t;
            int[] logs;

            RMQ(int[] a) {
                int n = a.length;
                logs = new int[n + 1];
                for (int i = 2; i <= n; i++) {
                    logs[i] = logs[i - 1];
                    while ((1 << logs[i]) <= i) {
                        ++logs[i];
                    }
                    --logs[i];
                }

                t = new int[logs[n] + 1][n];
                for (int log = 0; log < t.length; log++) {
                    for (int i = 0; i + (1 << log) <= n; i++) {
                        if (log == 0) {
                            t[log][i] = a[i];
                        } else {
                            t[log][i] = Math.max(t[log - 1][i], t[log - 1][i + (1 << (log - 1))]);
                        }
                    }
                }
            }

            int getMax(int l, int r) {
                if (l > r) {
                    return -1;
                }
                int log = logs[r - l + 1];
                return Math.max(t[log][l], t[log][r - (1 << log) + 1]);
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

