← 返回题目列表

Codeforces · 193/D

D. 两段

中文机器翻译题面 查看原题

Nick 有一些由 1 到 n 的 p 个整数组成的排列。线段 [l, r] (l ≤ r) 是满足 l ≤ i ≤ r 的元素 pi 的集合。

Nick 称一对线段 [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 说明符。

示例

输入 #1

3
1 2 3

输出 #1

3

输入 #2

5
1 4 5 3 2

输出 #2

10

输入 #3

5
5 4 3 1 2

输出 #3

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