D. Два отрезка
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

У Николая есть некоторая перестановка p целых чисел от 1 до n. Отрезком [l, r] (l ≤ r) называется множество элементов перестановки pi таких, что l ≤ i ≤ r.

Пару отрезков [a0, a1] и [b0, b1] (1 ≤ a0 ≤ a1 < b0 ≤ b1 ≤ n) Николай называет хорошей, если все их (a1 - a0 + b1 - b0 + 2) элементов, отсортированные в порядке возрастания, образуют арифметическую прогрессию с разностью 1. То есть, элементы, выписанные в отсортированном порядке образуют последовательность {x, x + 1, x + 2, ..., x + m - 1} для некоторых x и m.

Вам требуется найти в заданной перестановке количество различных пар хороших отрезков. Две пары отрезков считаются различными, если различны множества элементов, которые содержатся в этих парах отрезков. Например, любой отрезок [l, r] (l < r) может быть представлен в виде пары отрезков, как [l, i] и [i + 1, r] (l ≤ i ≤ r). Так как все эти пары образуют одно множество элементов, все они считаются одинаковыми.

Для лучшего понимания условия, смотрите комментарии к примерам.

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

В первой строке записано целое число n (1 ≤ n ≤ 3·105) — размер перестановки. Во второй строке через пробел записано n различных целых чисел pi, (1 ≤ pi ≤ n).

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

Выведите единственное число — количество хороших пар отрезков перестановки p.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
1 2 3
Выходные данные
3
Входные данные
5
1 4 5 3 2
Выходные данные
10
Входные данные
5
5 4 3 1 2
Выходные данные
10
Примечание

В первом примере подходят следующие пары отрезков: ([1, 1], [2, 2]); ([2, 2], [3, 3]); ([1, 2], [3, 3]). Пара отрезков ([1, 1], [2, 3]), по определению, эквивалентна паре ([1, 2], [3, 3]), так как обе эти пары соответствуют множеству элементов {1, 2, 3}.

В третьем примере подходят следующие пары отрезков: ([4, 4], [5, 5]); ([3, 3],[4, 5]); ([2, 2],[3, 5]); ([1, 1],[2, 5]); ([3, 3],[5, 5]); ([2, 3],[5, 5]); ([1, 3],[5, 5]); ([2, 2],[3, 3]); ([1, 1],[2, 3]); ([1, 1],[2, 2]).