|
Битоническая последовательность
(Время: 2 сек. Память: 32 Мб Сложность: 27%)
Последовательность [b1, b2, ..., bk] называется битонической, если выполнены неравенства
b1 < b2 < ... < bi > ... > bk для некоторого 1 ≤ i ≤ k.
Например, последовательности [1], [1, 2, 3, 2], [1, 4, 10], [3, 2] являются битоническими, а последовательности [1, 1], [2, 1, 3] — нет.
Задана последовательность [a1, a2, ..., an]. Требуется определить количество пар (l, r) таких, что
1 ≤ l ≤ r ≤ n и последовательность [al, al+1, ..., ar] является битонической.
Входные данные
Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 300 000).
Вторая строка ввода содержит n целых чисел: a1, a2, ..., an (1 ≤ ai ≤ n).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число — количество пар (l, r), таких, что 1 ≤ l ≤ r ≤ n и последовательность
[al, al+1, ..., ar] является битонической.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 1 1 2 3 1 | 11 |
2 | 3 1 1 1 | 3 |
Замечание
В первом примере подходят следующие пары:
- (1, 1), последовательность [1]
- (2, 2), последовательность [1]
- (2, 3), последовательность [1, 2]
- (2, 4), последовательность [1, 2, 3]
- (2, 5), последовательность [1, 2, 3, 1]
- (3, 3), последовательность [2]
- (3, 4), последовательность [2, 3]
- (3, 5), последовательность [2, 3, 1]
- (4, 4), последовательность [3]
- (4, 5), последовательность [3, 1]
- (5, 5), последовательность [1]
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |