Even Substrings

题意翻译

给你一个长度为$n$的字符串$s = s_1 s_2 \dots s_n$,该字符串仅由数字组成 求该字符串中有多少个连续的子串所代表的整数为偶数 如$s=1234$,有如下$6$种方案: * $s[1 \dots 2]=12$ * $s[2 \dots 2]=2$ * $s[1 \dots 4]=1234$ * $s[2 \dots 4]=234$ * $s[3 \dots 4]=34$ * $s[4 \dots 4]=4$

题目描述

You are given a string $ s=s_1s_2\dots s_n $ of length $ n $ , which only contains digits $ 1 $ , $ 2 $ , ..., $ 9 $ . A substring $ s[l \dots r] $ of $ s $ is a string $ s_l s_{l + 1} s_{l + 2} \ldots s_r $ . A substring $ s[l \dots r] $ of $ s $ is called even if the number represented by it is even. Find the number of even substrings of $ s $ . Note, that even if some substrings are equal as strings, but have different $ l $ and $ r $ , they are counted as different substrings.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1 \le n \le 65000 $ ) — the length of the string $ s $ . The second line contains a string $ s $ of length $ n $ . The string $ s $ consists only of digits $ 1 $ , $ 2 $ , ..., $ 9 $ .

输出格式


Print the number of even substrings of $ s $ .

输入输出样例

输入样例 #1

4
1234

输出样例 #1

6

输入样例 #2

4
2244

输出样例 #2

10

说明

In the first example, the $ [l, r] $ pairs corresponding to even substrings are: - $ s[1 \dots 2] $ - $ s[2 \dots 2] $ - $ s[1 \dots 4] $ - $ s[2 \dots 4] $ - $ s[3 \dots 4] $ - $ s[4 \dots 4] $ In the second example, all $ 10 $ substrings of $ s $ are even substrings. Note, that while substrings $ s[1 \dots 1] $ and $ s[2 \dots 2] $ both define the substring "2", they are still counted as different substrings.