Codeforces Round 122 (Div. 1) |
---|
Закончено |
У Николая есть некоторая перестановка 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]).
Название |
---|