CF193D.Two Segments

Nick 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.

尼克有一个由 $1$ 到 $n$ 的整数构成的排列 $p$。一个区间 $[l,\,r]$（其中 $l \le r$）是指满足 $l \le i \le r$ 的所有元素 $p_i$ 构成的集合。

尼克称一对区间 $[a_0,\,a_1]$ 和 $[b_0,\,b_1]$（满足 $1 \le a_0 \le a_1 < b_0 \le b_1 \le n$）为好对，当且仅当这两个区间中全部 $a_1 - a_0 + b_1 - b_0 + 2$ 个元素按升序排列后，构成一个公差为 $1$ 的等差数列。即：将这些元素升序排列后，其形式为 $\{x,\,x+1,\,x+2,\,\dots,\,x+m-1\}$，其中 $x$ 和 $m$ 为某些整数。

你的任务是求出给定排列中不同的好对区间的数量。若两对区间所包含的元素集合不同，则认为它们是不同的；反之则视为相同。例如，任意区间 $[l,\,r]$（其中 $l < r$）可被划分为多对区间 $[l,\,i]$ 和 $[i+1,\,r]$（其中 $l \le i \le r$）。由于所有这些划分方式对应的元素集合完全相同，因此它们被视为同一对。

有关样例测试的进一步说明，请参见附带的注释。

The first line contains integer n (1 ≤ n ≤ 3·105) — the permutation size. The second line contains n space-separated distinct integers p__i, (1 ≤ p__i ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）—— 排列的长度。
第二行包含 $n$ 个用空格分隔的互不相同的整数 $p_i$（$1 \leq p_i \leq 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.

输出一个整数——排列 $p$ 中“好”线段对的数量。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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

在第一个样例中，以下线段对是合法的：$[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]$。