CF193D Two Segments

Nick 有一个排列 $p$，包含从 $1$ 到 $n$ 的 $n$ 个整数。一个区间 $[l,r]$（$l \leq r$）是所有满足 $l \leq i \leq r$ 的 $p_i$ 组成的集合。 Nick 把一对区间 $[a_0,a_1]$ 和 $[b_0,b_1]$（$1 \leq a_0 \leq a_1 < b_0 \leq b_1 \leq n$）称为“好”的，如果这两个区间共计 $a_1-a_0+b_1-b_0+2$ 个元素，按升序排列后，这些元素能组成首项为 $x$ 的等差为 $1$ 的数列，即有某个 $x$ 和 $m$ 使这组数为 $\{x, x+1, x+2, \ldots, x+m-1\}$。 你的任务是，计算在给定排列 $p$ 中不同的好区间对的数量。两对区间被认为不同，当且仅当这两对区间包含的元素集合不同。例如，任意区间 $[l,r]$（$l < r$）可以表示为一对区间 $[l,i]$ 和 $[i+1,r]$（$l \leq i < r$）。由于这些划分包含的元素集合是一样的，因此都视为相同的区间对。 具体参见样例说明。

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示排列的大小。 第二行包含 $n$ 个两两不同的整数 $p_i$（$1 \leq p_i \leq n$），表示该排列。

输出一个整数，表示排列 $p$ 中不同的好区间对的数量。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。建议使用 cin、cout 流或者 %I64d 格式控制符。

在第一个样例中，以下区间对是好的：（$[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]$）。 由 ChatGPT 5 翻译