Амир, Тамер и Волшебная Донерка

C. Амир, Тамер и Волшебная Донерка
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Таханди - волшебная донерка, которая дает силу всем информатикам Yosik-a. Как-то раз Амир и Тамер, великие братья, решили пойти туда и поесть донер. Когда они пришли в Таханди они были крайне удивлены что на кассе стоял их абишка - Нурали. Нурали, как истинный абишка, хочет чтобы его хазики чалили и поэтому сказал что даст им донеры только если они решат его задачу. Амир и Тамер еще только начинающие олимпиадники и поэтому задача показалась им крайне тяжелой. Расстроенные они пришли к вам и попросили вас помочь им с этой задачей.

Дается массив a
длинны n
, надо посчитать количество способов разделить его на три непрерывных подотрезка чтобы максимальные числа всех трех подотрезков были равны.

Входные данные
В первой строке входных данных находится целое число n≤105
. Во второй строке вводится массив a (a_i≤10⁹) для всех (1≤i≤n)

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

Group Add. constraints Points
1
n=3
8
2
n≤100
10
3
n≤5000
20
4
ai=1 для всех (1≤i≤n) 20 5
— 42

0