Two Segments
Description
Nick has some permutation consisting of p integers from 1 to n. A segment [l, r] (l ≤ r) is a set of elements pi satisfying l ≤ i ≤ r.
Nick calls a pair of segments [a0, a1] and [b0, b1] (1 ≤ a0 ≤ a1 < b0 ≤ b1 ≤ n) good if all their (a1 - a0 + b1 - b0 + 2) elements, when sorted in ascending order, form an arithmetic progression with a difference of 1. That is, when they sorted in ascending order, the elements are in the form {x, x + 1, x + 2, ..., x + m - 1}, for some x and m.
Your task is to find the number of distinct pairs of good segments in the given permutation. Two pairs of segments are considered distinct if the sets of elements contained in these pairs of segments are distinct. For example, any segment [l, r] (l < r) can be represented as a pair of segments, as [l, i] and [i + 1, r] (l ≤ i ≤ r). As all these pairs consist of the same set of elements, they are considered identical.
See the notes accompanying the sample tests for clarification.
The first line contains integer n (1 ≤ n ≤ 3·105) — the permutation size. The second line contains n space-separated distinct integers pi, (1 ≤ pi ≤ n).
Print a single integer — the number of good pairs of segments of permutation p.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Input
The first line contains integer n (1 ≤ n ≤ 3·105) — the permutation size. The second line contains n space-separated distinct integers pi, (1 ≤ pi ≤ n).
Output
Print a single integer — the number of good pairs of segments of permutation p.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Samples
3
1 2 3
3
5
1 4 5 3 2
10
5
5 4 3 1 2
10
Note
In the first sample the following pairs of segments are good: ([1, 1], [2, 2]); ([2, 2], [3, 3]); ([1, 2], [3, 3]). Pair of segments ([1, 1], [2, 3]) is by definition equivalent to pair ([1, 2], [3, 3]), since both of them covers the same set of elements, namely {1, 2, 3}.
In the third sample the following pairs of segments are good: ([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]).