← 返回题目列表

Codeforces · 526/F

F. 布丁怪物

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

在这个问题中,您将遇到游戏布丁怪物的简化模型。

开发任何游戏的一个重要过程就是创建关卡。 Pudding Monsters 中的游戏场是一个 n × n 的矩形网格,其中 n 个单元格包含怪物,其他一些单元格包含游戏对象。游戏玩法是让怪物在场上移动。当两个怪物相互接触时,它们会粘在一起形成一个大怪物(就像它们来自布丁,还记得吗?)。

统计数据显示,如果最初每一行和每一列都包含一个怪物,并且其余的地图细节是通过其他游戏对象的正确定位来设置的,那么最有趣的地图就会出现。

一种广泛用于提高开发过程效率的技术是重用可用资源。例如,如果有一张大的 n × n 地图,您可以在其中选择一个较小的 k × k 正方形部分,恰好包含 k 个怪物,并将其建议为原始地图的简化版本。

你想知道有多少种方法可以在初始地图中选择一个 k × k (1 ≤ k ≤ n) 的方形碎片,其中正好包含 k 个布丁怪物。计算这个数字。

输入

第一行包含一个整数 n (1 ≤ n ≤ 3 × 105) — 初始字段的大小。

接下来的 n 行包含最初包含怪物的单元格的坐标。接下来的第 i 行包含两个数字 ri, ci (1 ≤ ri, ci ≤ n) — 最初包含第 i 个怪物的单元格的行号和列号。

保证所有 ri 都是不同的数字,所有 ci 都是不同的数字。

输出

打印原始字段中可以形成新地图的不同正方形片段的数量。

示例

输入 #1

5
1 1
4 3
3 2
2 4
5 5

输出 #1

10