Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

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

Айбар и Данияр решили купить шоколадки перед олимпиадой. Допустим, в магазине продаются $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, . . . , b_n$.

Теперь друзьям стало интересно, сколько есть пар $1 \leq i \leq j \leq n$ таких, что если друзья будут покупать шоколадки только среди видов $(i, . . . , j)$ победит дружба?

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

В первой строке дано одно целое число $n$ — количество видов шоколадок в супермаркете $(2 \leq n \leq 250000)$.

Во второй строке даны $n$ чисел $b_1, . . . , b_n (1 \leq b_i \leq 10^9)$.

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

Выведите одно целое число — ответ на задачу

Система оценки

Примеры

Ввод

3
1 2 3

Вывод

3

Ввод

5
1 1 3 2 1

Вывод

6