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.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Coding {

    private static BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static Pair[] segmentTree = new Pair[4*200000 + 11];

    public static void main(String[] args) {
        try {
            run();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void run() throws Exception {
        InputModule inp = new InputModule();
        OutputModule out = new OutputModule();
        int t = 1;
        while (t > 0) {
            int len = inp.cinInt();
            String ss = bi.readLine();
            long[] fn = new long[len+1];
            fn[1] = 1;
            for(int i=2;i<=len;++i) {
                long val = i;
                val = val*(i+1);
                val/=2;
                fn[i] = fn[i-1] + val;
            }
            int oneCount = 0;
            List<Pair> ones = new ArrayList<>();
            long ans = 0;
            for(int i=0;i<len;++i) {
                if (ss.charAt(i)=='1') {
                    oneCount++;
                } else {
                    if (oneCount>0) {
                        ones.add(new Pair(oneCount, i-oneCount));
                        if (oneCount>2) {
                            ans+=fn[oneCount-2];
                        }
                        oneCount = 0;
                    }
                }
            }
            if (oneCount>0) {
                ones.add(new Pair(oneCount, len - oneCount));
                if (oneCount>2) {
                    ans+=fn[oneCount-2];
                }
            }

            //System.out.println(" ans is " + ans);

            // Check for left substrings
            int[] nearest = new int[len+2];
            int[] startPointsL = new int[len+2];
            for(int i=1;i<=len+1;++i) {
                nearest[i] = -1;
            }

            for(int i=0;i<ones.size();++i) {
                int val = ones.get(i).count;
                int start = ones.get(i).start;
                for(int j=1;j<=val-1;++j) {
                    int idxStart = nearest[j]+1;
                    long prod = (start-idxStart+1);
                    prod*=j;
                    ans+=prod;
                }
                //System.out.println(i + " " + ans);
                // Add start points for selecting entire cluster
                int idxStart = nearest[val]+1;
                startPointsL[i] = start-idxStart+1;
                //System.out.println(i + " " + startPointsL[i]);

                for(int j=1;j<=val;++j) {
                    nearest[j] = start + val-j;
                }
            }

            // Check for right subtrings
            for(int i=1;i<=len+1;++i) {
                nearest[i] = len;
            }

            for(int i=ones.size()-1;i>=0;--i) {
                int val = ones.get(i).count;
                int start = ones.get(i).start;
                int end = start + val-1;
                for(int j=1;j<=val-1;++j) {
                    long prod = ((nearest[j+1]-1) - end +1);
                    prod*=j;
                    ans+=prod;
                }
                //System.out.println(i + " " + ans);
                // End points for selecting entire cluster
                int endPoints = (nearest[val+1]-1)-end+1;
                long prod = startPointsL[i];
                prod*=endPoints;
                prod*=val;
                //System.out.println("End points is " + endPoints);
                ans+=prod;
                //System.out.println(i + " add global " + ans);
                for(int j=1;j<=val;++j) {
                    nearest[j] = start + j-1;
                }
            }


            out.printLong(ans);
            t--;
        }
    }

    private static class InputModule {
        private int cinInt() throws Exception {
            return Integer.parseInt(bi.readLine().split(" ")[0].trim());
        }

        private long cinLong() throws Exception {
            return Long.parseLong(bi.readLine().split(" ")[0].trim());
        }

        private Double cinDouble() throws Exception {
            return Double.parseDouble(bi.readLine().split(" ")[0].trim());
        }

        private int[] cinIntArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            int[] ar = new int[n];
            for (int i = 0; i < n; ++i) {
                ar[i] = Integer.parseInt(values[i]);
            }
            return ar;
        }

        private long[] cinLongArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            long[] ar = new long[n];
            for (int i = 0; i < n; ++i) {
                ar[i] = Long.parseLong(values[i]);
            }
            return ar;
        }
    }

    private static class OutputModule {
        private void printInt(int ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printLong(long ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printDouble(Double ans) throws Exception {
            writer.append(String.format("%.10f", ans));
            writer.append("\n");
            writer.flush();
        }

        private void printIntArray(int[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }

        private void printLongArray(long[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }
    }

    private static class Pair {
        int count;
        int start;
        public Pair(int count, int start) {
            this.count = count;
            this.start = start;
        }
    }
}