题目描述

对于正整数 $h,w$，我们用 $(h,w)$ 表示一个纵边长为 $h$，横边长为 $w$ 的长方形。注意，本题中不考虑长方形的旋转操作，当 $h\neq w$ 时，长方形 $(h,w)$ 与长方形 $(w,h)$ 被视为不同的长方形。

一个长方形序列 $((h_1,w_1),(h_2,w_2),\dots,(h_n,w_n))$ 被称为长方形生成列，当且仅当存在如下操作方法使得操作能够成功：

• 令长方形 $X$ 为 $(h_1,w_1)$。在以下过程中，记当前长方形 $X$ 的纵边长和横边长分别为 $H,W$。
• 对于 $i=2,3,\dots,n$，依次进行以下两种操作中的一种。如果两种都无法进行，则操作失败，过程结束。
  • 若 $X$ 的纵边长等于 $h_i$，则将长方形 $(h_i,w_i)$ 横向拼接到 $X$ 上。即，此时 $H=h_i$，将 $X$ 替换为 $(H,W+w_i)$。
  • 若 $X$ 的横边长等于 $w_i$，则将长方形 $(h_i,w_i)$ 纵向拼接到 $X$ 上。即，此时 $W=w_i$，将 $X$ 替换为 $(H+h_i,W)$。
• 若上述一系列操作均未失败，则操作成功，过程结束。

---

给定 $N$ 个长方形，第 $i$ 个长方形的纵边长为 $H_i$，横边长为 $W_i$。

请计算满足 $1\leq l\leq r\leq N$，且长方形序列 $((H_l,W_l),(H_{l+1},W_{l+1}),\dots,(H_r,W_r))$ 是长方形生成列的整数对 $(l,r)$ 的个数。

输入格式

输入按以下格式从标准输入读入：

$N$
$H_1$ $W_1$
$H_2$ $W_2$
$\vdots$
$H_N$ $W_N$

输出格式

输出答案。

样例 1

输入

4
1 2
1 3
2 3
3 1

输出

7

样例 2

输入

5
2 1
2 1
1 2
3 2
1 4

输出

10

样例 3

输入

1
1000000 1000000

输出

1

样例 4

输入

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

输出

55

说明/提示

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq H_i,W_i\leq 10^6$
• 输入的所有值均为整数。

样例解释 1

满足条件的 $(l,r)$ 有 $7$ 个，分别为 $(1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4)$。例如，对于 $(l,r)=(2,4)$，若依次进行纵向拼接 $\to$ 横向拼接，则操作可以成功。

由 ChatGPT 4.1 翻译