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.*;

public class F2 { 

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		char[] s = sc.next().toCharArray();
		long[] arr = new long[n];
		SegmentTree sgt = new SegmentTree(arr);
		long res = 0;
//		long count = 0;
		LinkedList<Integer> q = new LinkedList<>();		
		LinkedList<Integer> q_ = new LinkedList<>();
		for(int i = 0; i < n; i++) {
			if(s[i] == '1') {
//				count++;
				if(q.isEmpty()) {
					sgt.update(0, i, 1);
				}
				else {
					int p = q.removeLast();
					sgt.update(p+1, i, 1);
				}
				q_.add(i);
			}
			else {
				if(i > 0 && s[i-1] == '1') {
					while(!q_.isEmpty()) {
						q.add(q_.removeFirst());
					}
				}
			}
			long curr = sgt.querySum(0, n);
			res += curr;
		}
 		System.out.println(res);
	}
	
	static class SegmentTree { /* Author: Po-Chun Chiu */
		int size;
		private long[] sum;
		private long[] lazy;


		public SegmentTree(long[] array){
			size = array.length;
			sum = new long[array.length*4];
			lazy = new long[array.length*4];
			buildTree(array, 1, 0, size - 1);
		}

		private void buildTree(long[] array, int position, int front, int end){
			//Basis case for returning the elements itself
			if(front == end){
				sum[position] = array[front];
				return;
			}
			//Building trees by dividing into two subtrees
			buildTree(array, position * 2, front, (front+end)/2);
			buildTree(array, position * 2 + 1, (front+end)/2 + 1, end);

			recalc(position, front, end);
		}

		private void recalc(int position, int front, int end) {
			sum[position] = getSum(position * 2, front, (front+end)/2) + getSum(position * 2 + 1, (front+end)/2 + 1, end);
		}

		private long getSum(int position,int front,int end){
			return sum[position] + lazy[position] * (end - front + 1);
		}

		public long querySum(int queryFront, int queryEnd) {
			return querySum(1, 0, size-1, queryFront, queryEnd);
		}

		private long querySum(int position,int front,int end, int queryFront, int queryEnd){
			//Case for entirely inclusive
			if(front>=queryFront&&queryEnd>=end){
				return getSum(position,front,end);
			}
			//Case for entirely exclusive
			if(end<queryFront||queryEnd<front){
				return 0;
			}
			propagate(position,front,end);
			long leftAns = querySum(position*2,front,(front+end)/2,queryFront,queryEnd);
			long rightAns = querySum(position*2+1,(front+end)/2+1,end,queryFront,queryEnd);
			return leftAns+rightAns;
		}


		private void propagate(int position, int front, int end){
			lazy[position * 2] += lazy[position];
			lazy[position * 2 + 1] += lazy[position];
			sum[position] = getSum(position, front, end);
			lazy[position] = 0;
			//Set the propagation to 0 so that it will not propagate the value again and again
		}

		public void update(int updateFront, int updateEnd, long delta){
			update(1, 0, size - 1, updateFront, updateEnd, delta);
		}

		private void update(int position, int front, int end, int updateFront, int updateEnd, long value){
			//Case for entirely inclusive
			if(front >= updateFront && updateEnd >= end){
				lazy[position]+=value;
				return;
			}
			//Case for entirely exclusive
			if(end < updateFront || updateEnd < front){
				return;
			}
			propagate(position, front, end);
			update(position * 2, front, (front+end)/2, updateFront, updateEnd, value);
			update(position * 2 + 1, (front+end)/2 + 1, end, updateFront, updateEnd, value);
			recalc(position, front, end);
		}
	}
	
	static class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public FastScanner() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
        	return Long.parseLong(next());
        }
        public double nextDouble() {
        	return Double.parseDouble(next());
        }
        public String nextLine() {
        	try {
        		return reader.readLine();
        	} catch(IOException e) {
        		throw new RuntimeException(e);
        	}
        }
    }

}
