No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Two Segments

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNick has some permutation consisting of *p* integers from 1 to *n*. A segment [*l*, *r*] (*l* ≤ *r*) is a set of elements *p*_{i} satisfying *l* ≤ *i* ≤ *r*.

Nick calls a pair of segments [*a*_{0}, *a*_{1}] and [*b*_{0}, *b*_{1}] (1 ≤ *a*_{0} ≤ *a*_{1} < *b*_{0} ≤ *b*_{1} ≤ *n*) good if all their (*a*_{1} - *a*_{0} + *b*_{1} - *b*_{0} + 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.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 3·10^{5}) — the permutation size. The second line contains *n* space-separated distinct integers *p*_{i}, (1 ≤ *p*_{i} ≤ *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.

Examples

Input

3

1 2 3

Output

3

Input

5

1 4 5 3 2

Output

10

Input

5

5 4 3 1 2

Output

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]).

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/13/2021 15:11:58 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|