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

Есеп E. Шоколадтар

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

2.5 seconds

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

256 megabytes

Айбар мен Данияр олимпиада алдында шоколад сатып алуды шешті. Дүкенде $1$-ден $n$-ға дейін нөмірленген шоколадтардың $n$ түрі сатылады делік. Шоколадтың $i$-нші түрінде $a_i$ тәттілік деңгейі бар. Айбар мен Данияр келесі қарапайым схема бойынша шоколад сатып алуға келісті:

• Алдымен Айбар ең тәтті шоколадты сатып алады. Сонда Данияр да шоколадтың басқа түрлерінің ішінде ең тәтті шоколадты алады. Ресми түрде айтқанда, Айбар түрі $i$ болатын шоколадты алса, Данияр түрі $j \neq i$ болатын тәттілігі ең жоғары шоколадты сатып алуы керек.
• Енді Айбар тәттілігі ең төмен шоколадты сатып алады. Содан кейін Данияр да шоколадтың басқа түрлерінің ішінде тәттілігі ең кішкентай шоколадты сатып алады. Ресми түрде айтқанда, Айбар түрі $i$ болатын шоколадты алса, Данияр түрі $j \neq i$ болатын тәттілігі ең төмен шоколадты сатып алуы керек.

Соңында Айбар мен Данияр сатып алған шоколадтарының тәттіліктерінің қосындысын санайды. Егер олардың есептелген қосындысы бірдей болса, онда достық жеңеді. Мысалы, егер дүкен тәттілік деңгейлері $[1, 4, 6, 3]$ болатын шоколадтың $n = 4$ түрін сатса, Айбар жалпы тәттілігі $6 + 1 = 7$ болатын $3$ және $1$ шоколадтарын сатып алар еді. Ал Данияр жалпы тәттілігі $4 + 3 = 7$ болатын $2$ және $4$ шоколадтарын сатып алып, соңында достық жеңетін еді. Бұл есепте әр түрдің кем дегенде екі шоколады бар деп есептеуге болады. Дүкенде тек $n = 2$ шоколад түрі болса, достардың екеуі де $1$ және $2$ түрінен бір шоколадтан сатып алар еді. Достар ұсақ-түйек болмай, бірден супермаркетке баруды шешті. Супермаркетте тәттілік деңгейлері $b_1, \ldots, b_n$ болатын $n$ шоколад түрлері сатылады. Енді достар қызықты: егер олар шоколадтарды $(i, \ldots, j)$ түрлерінің арасында ғана сатып алатын болса, достық жеңетіндей қанша $1 <= i < j <= n$ жұп бар?

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

Бірінші жолда $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 )