4-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача E. Шоколадки

Ограничение по времени:

2.5 секунд

Ограничение по памяти:

256 мегабайт

Айбар и Данияр решили купить шоколадки перед олимпиадой. Допустим, в магазине продаются $n$ видов шоколадок пронумерованных от $1$ до $n$. У каждого вида шоколадки $i$ есть свой уровень сладости $a_i$. Айбар и Данияр договорились покупать шоколадки по следующей нехитрой схеме:

• Сперва Айбар купит шоколадку с самой большой сладостью. Затем Данияр тоже купит шоколадку с самой большой сладостью среди других видов шоколадок. Более формально, если Айбар купил шоколадку вида $i$, Данияр должен купить шоколадку вида $j \neq i$ такую, что её сладость самая большая.
• Теперь Айбар купит шоколадку с самой маленькой сладостью. Затем Данияр тоже купит шоколадку с самой маленькой сладостью среди других видов шоколадок. Более формально, если Айбар купил шоколадку вида $i$, Данияр должен купить шоколадку вида $j \neq i$ такую, что её сладость самая маленькая.

В конце Айбар и Данияр суммируют сладости купленных ими шоколадок. Если их посчитанные суммы оказываются одинаковыми, то побеждает дружба. Например, если бы в магазине продавали $n = 4$ видов шоколадок со сладостями $[1, 4, 6, 3]$, то Айбар бы купил шоколадки вида $3$ и $1$ с суммарной сладостью $6 + 1 = 7$. А Данияр бы купил шоколадки вида $2$ и $4$ с суммарной сладостью $4 + 3 = 7$ и в конце победила бы дружба. В этой задаче можно считать что есть не менее двух шоколадок каждого вида. Если бы в магазине было всего лишь $n = 2$ видов шоколадок, они оба купили бы по одной шоколадке вида $1$ и $2$. Друзья решили не мелочиться и сразу зайти в супермаркет. В супермаркете продаются $n$ видов шоколадок со сладостями $b_1, \ldots, b_n$. Теперь друзьям стало интересно, сколько есть пар $1 <= i < j <= n$ таких, что если друзья будут покупать шоколадки только среди видов $(i, \ldots, j)$ победит дружба?

Формат входного файла

В первой строке дано одно целое число $n$ — количество видов шоколадок в супермаркете ($2 <= n <= 250000$). Во второй строке даны $n$ чисел $b_1, \ldots, b_n$ ($1 <= b_i <= 10^9$).

Формат выходного файла

Выведите одно целое число — количество искомых пар.

Примеры:

Вход

3
1 2 3

Ответ

3

Вход

5
1 1 3 2 1

Ответ

6

Замечание

Во втором примере, подходят следующие пары: $(1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)$ ( Temirlan Baibolov )