给定一个字符串 $$$s=s_1s_2\dots s_n$$$,长度为 $$$n$$$,其中仅包含数字 $$$1$$$、$$$2$$$、...、$$$9$$$。
$$$s$$$ 的子串 $$$s[l \dots r]$$$ 是字符串 $$$s_l s_{l + 1} s_{l + 2} \ldots s_r$$$。 $$$s$$$ 的子串 $$$s[l \dots r]$$$ 被调用,即使它代表的数字是偶数。
求 $$$s$$$ 的偶数子串的数量。请注意,即使某些子字符串与字符串相同,但具有不同的 $$$l$$$ 和 $$$r$$$,它们也会被视为不同的子字符串。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 65000$$$) — 字符串 $$$s$$$ 的长度。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。字符串 $$$s$$$ 仅包含数字 $$$1$$$、$$$2$$$、...、$$$9$$$。
输出
打印 $$$s$$$ 的偶数子串的数量。
示例
输入 #1
4 1234
输出 #1
6
输入 #2
4 2244
输出 #2
10
注意
在第一个示例中,偶数子串对应的 $$$[l, r]$$$ 对是:
- $$$s[1 \点 2]$$$
- $$$s[2 \点 2]$$$
- $$$s[1 \点 4]$$$
- $$$s[2 \点 4]$$$
- $$$s[3 \点 4]$$$
- $$$s[4 \点 4]$$$
在第二个示例中,$$$s$$$ 的所有 $$$10$$$ 子串都是偶数子串。请注意,虽然子字符串 $$$s[1 \dots 1]$$$ 和 $$$s[2 \dots 2]$$$ 都定义了子字符串“2”,但它们仍然被视为不同的子字符串。