Задача 0R. 52 ≡

Условие

Замечали ли Вы когда-нибудь то, что на электронном циферблате цифры 5 и 2 очень сильно похожи? А точнее, что они зеркальны друг другу?

У Жени есть длинный циферблат, на котором светятся n цифр, причем все цифры являются либо пятёркой, либо двойкой. Женя хочет отрезать какую-либо полоску из этого циферблата (то есть выбрать какое-то количество подряд идущих цифр) и подарить ее Анжелике. Анжелика любит во всем красоту, поэтому она хочет получить в подарок такую полоску, которая имеет четную длину и которая симметрична относительно центра. Более формально, полоска s длины 2k Анжелике понравится, если для любого 1 ≤ i ≤ 2k выполняется одно из двух условий:

1. s_i = 5, s_2k − i = 2
2. s_i = 2, s_2k − i = 5

Помогите Жене! Сообщите, сколькими способами он может отрезать полоску, чтобы подарить ее Анжелике.

Формат входных данных

В первой строке вводится число n — количество цифр на полоске (1 ≤ n ≤ 5 * 10⁵). В следующей строке вводится n цифр, которые показывают, в каком порядке светятся цифры на циферблате.

Гарантируется непротиворечивость входных данных, то есть во второй строке входных данных каждый символ является либо пятеркой, либо двойкой.

Формат выходных данных

Выведите ответ на задачу.

Примеры тестов

8
52525252

16

5
52525

6

2
52

1