Битоническая последовательность

Последовательность [b₁, b₂, ..., b_k] называется битонической, если выполнены неравенства b₁ < b₂ < ... < b_i > ... > b_k для некоторого 1 ≤ i ≤ k.

Например, последовательности [1], [1, 2, 3, 2], [1, 4, 10], [3, 2] являются битоническими, а последовательности [1, 1], [2, 1, 3] — нет.

Задана последовательность [a₁, a₂, ..., a_n]. Требуется определить количество пар (l, r) таких, что 1 ≤ l ≤ r ≤ n и последовательность [a_l, a_l+1, ..., a_r] является битонической.

Входные данные

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 300 000).

Вторая строка ввода содержит n целых чисел: a₁, a₂, ..., a_n (1 ≤ a_i ≤ n).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число — количество пар (l, r), таких, что 1 ≤ l ≤ r ≤ n и последовательность [a_l, a_l+1, ..., a_r] является битонической.

Примеры

Замечание

В первом примере подходят следующие пары:

• (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]

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]