Автор: | Женя Татаринов | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход |
Замечали ли Вы когда-нибудь то, что на электронном циферблате цифры 5 и 2 очень сильно похожи? А точнее, что они зеркальны друг другу?
У Жени есть длинный циферблат, на котором светятся n цифр, причем все цифры являются либо пятёркой, либо двойкой. Женя хочет отрезать какую-либо полоску из этого циферблата (то есть выбрать какое-то количество подряд идущих цифр) и подарить ее Анжелике. Анжелика любит во всем красоту, поэтому она хочет получить в подарок такую полоску, которая имеет четную длину и которая симметрична относительно центра. Более формально, полоска s длины 2k Анжелике понравится, если для любого 1≤i≤2k выполняется одно из двух условий:
Помогите Жене! Сообщите, сколькими способами он может отрезать полоску, чтобы подарить ее Анжелике.
В первой строке вводится число n — количество цифр на полоске (1≤n≤5∗105). В следующей строке вводится n цифр, которые показывают, в каком порядке светятся цифры на циферблате.
Гарантируется непротиворечивость входных данных, то есть во второй строке входных данных каждый символ является либо пятеркой, либо двойкой.
Выведите ответ на задачу.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|