← 返回题目

题库练习 Infinite Inversions

← 上一题下一题 →

A9958 | $Infinite Inversions$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

There is an infinite sequence consisting of all positive integers in the increasing order: $p={1,2,3,...}$ . We performed $n$ swap operations with this sequence. A $swap(a,b)$ is an operation of swapping the elements of the sequence on positions $a$ and $b$ . Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs $(i,j)$ , that $i<j$ and $p_{i}>p_{j}$ .

输入格式

The first line contains a single integer $n$ ( $1<=n<=10^{5}$ ) — the number of swap operations applied to the sequence. Each of the next $n$ lines contains two integers $a_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=10^{9}$ , $a_{i}≠b_{i}$ ) — the arguments of the swap operation.

输出格式

Print a single integer — the number of inversions in the resulting sequence.

输入输出样例

输入 #1

2
4 2
1 4

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出