题目内容

小塔的游戏有一个长度为$k$且只包含字符$0$和$1$字符串，下标为$1$到$k$。

定义其权值为：每次操作可以选择一个下标$i$($1≤i≤k$)，将[$1,i$]的字符全部取反($0$变$1$,$1$变$0$)。将字符串变为全$1$的最少操作次数。

例如字符串$00110$，第一次操作选择$i=5$，字符串变成$11001$，第二次操作选择$i=4$，字符串变成$00111$，第三次操作选择$i=2$，字符串变成$11111$。至少需要$3$次操作，字符串权值为$3$。

给出一个长度为$n$的$01$字符串，问：有多少个长度为奇数的非空子串的权值是奇数(子串是该字符串中任意连续字符组成的字符串)？

定义子串为，从原字符串中，连续的选择一段字符(可以全选，可以不选)组成的新字符串。

输入描述

第一行包含一个整数$n$($1≤n≤10^5$)，表示字符串长度。

第二行包含一个长度为$n$的$01$字符串

输出描述

输出包含一行一个整数，表示长度和权值都是奇数的非空子串数量。

样例1

输入

5
01010

输出

6

说明

长度为$1$的子串有[$0,1,0,1,0$]，权值分别为[$1,0,1,0,1$]，奇数的有$3$个。

长度为$3$的子串有[$010,101,010$]，权值分别为[$3,2,3$]，奇数的有$2$个。

长度为$5$的子串有[$01010$]，权值分别为[$5$]，奇数的有$1$个。

长度为奇数的子串中，权值为奇数的总共有$3+2+1=6$