A. Чётные подстроки
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s=s_1s_2\dots s_n$$$ длины $$$n$$$, содержащая только цифры $$$1$$$, $$$2$$$, ..., $$$9$$$.

Подстрокой $$$s[l \dots r]$$$ строки $$$s$$$ назовём строку $$$s_l s_{l + 1} s_{l + 2} \ldots s_r$$$. Подстрока $$$s[l \dots r]$$$ строки $$$s$$$ называется чётной, если число, которое соответствует этой подстроке является чётным.

Найдите количество чётных подстрок строки $$$s$$$. Обратите внимание, что если некоторые подстроки равны как строки, но определены разными числами $$$l$$$, $$$r$$$, то они считаются различными.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 65000$$$) — длину строки $$$s$$$.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$. Строка $$$s$$$ состоит только из цифр $$$1$$$, $$$2$$$, ..., $$$9$$$.

Выходные данные

Выведите одно целое число — количество чётных подстрок в строке $$$s$$$.

Примеры
Входные данные
4
1234
Выходные данные
6
Входные данные
4
2244
Выходные данные
10
Примечание

В первом примере следующие $$$[l, r]$$$ пары задают чётные подстроки:

  • $$$s[1 \dots 2]$$$
  • $$$s[2 \dots 2]$$$
  • $$$s[1 \dots 4]$$$
  • $$$s[2 \dots 4]$$$
  • $$$s[3 \dots 4]$$$
  • $$$s[4 \dots 4]$$$

Во втором примере, все $$$10$$$ подстрок строки $$$s$$$ являются чётными. Обратите внимание, что не смотря на то, что строки $$$s[1 \dots 1]$$$ и $$$s[2 \dots 2]$$$ задают подстроку «2», они всё равно считаются как различные подстроки.