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.*;
import java.util.*;
import java.math.*;
 
//Sub_To_Errichto
public class Main {
    static final long MOD = 1000000007L;
    //static final long MOD = 998244353L;
    static final int INF = 50000000;
    static final int NINF = -500000000;
 
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        
    	int N = sc.ni();
    	String s = sc.next();
    	BinaryIndexedTree bit = new BinaryIndexedTree(N+1);
    	long ans = 0;
    	long cur = 0;
    	int one = 0;
    	for (int i = 0; i < N; i++) {
    		if (s.charAt(i)=='0') {
    			one = 0;
    			ans += cur;
    			continue;
    		}
    		one++;
    		
    		//binary search for the first index whose value is LESS than "one"
    		int low = 0;
    		int high = i;
    		while (low < high) {
    			int med = (low+high)/2;
    			if (bit.sum(0, med) >= one)
    				low = med+1;
    			else
    				high = med;
    		}
    		bit.add(1,low);
    		bit.add(-1,i+1);
    		cur += (i-low+1);
    		ans += cur;
    	}
    	pw.println(ans);
    	pw.close();
    }
    
    static class BinaryIndexedTree {
    	public int[] arr;

    	public BinaryIndexedTree (int N) {
    		arr = new int[N+1];
    	}

    	//add k to the i-th element.
    	public void add(int k, int i) {
    		int node = i+1;
    		while (node < arr.length) {
    			arr[node] += k;
    			node += node & (-node);
    		}
    	}

    	//sum up the elements from input[s_i] to input[e_i], from [s_i,e_i].
    	public int sum(int s_i, int e_i) {
    		return sum(e_i+1) - sum(s_i);
    	}

    	private int sum(int i) {
    		int total = 0;
    		int node = i;
    		while (node > 0) {
    			total += arr[node];
    			node -= node & (-node);
    		}
    		return total;
    	}
    }
 
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int ni() {
            return Integer.parseInt(next());
        }
 
        long nl() {
            return Long.parseLong(next());
        }
 
        double nd() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}