← 返回题目列表

Codeforces · 540/E

E. 无限反转

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

存在一个由所有正整数按递增顺序组成的无限序列:p = {1, 2, 3, ...}。我们用这个序列执行了 n 次交换操作。 swap(a, b) 是交换位置 a 和 b 上的序列元素的操作。您的任务是找到结果序列中的反转数量,即此类索引对 (i, j) 的数量,即 i < j 且 pi > pj。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 应用于序列的交换操作的数量。

接下来的 n 行中的每一行都包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) - 交换操作的参数。

输出

打印单个整数 — 结果序列中的反转次数。

示例

输入 #1

2
4 2
1 4

输出 #1

4

输入 #2

3
1 6
3 4
2 5

输出 #2

15

注意

在第一个示例中,序列修改如下:$$\{1,2,3,4,5,\ldots\} \rightarrow \{1,4,3,2,5,\ldots\} \rightarrow \{2,4,3,1,5.\ldots\}$$。它有 4 个由索引对 (1, 4)、(2, 3)、(2, 4) 和 (3, 4) 形成的反转。