Задача 0R. 52

Автор:Женя Татаринов   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

  1. si = 5, s2k − i = 2
  2. si = 2, s2k − i = 5

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
8
52525252
16
2
5
52525
6
3
2
52
1

0.088s 0.009s 15