题目描述

曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。隆冬的十一月，天气突然回暖，刮起了东南风。没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。曹操气急败坏地把你找来说：「快派船舰到江上，看看赤壁之战里有多少里被烧了。」

输入格式

第一行一个整数 $n$，表示有 $n$ 个着火点。

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示着火的区间是 $[a_i, b_i)$。

输出格式

一行一个整数，表示被烧的总长度。

数据范围

$1 \le n \le 2\times 10^4$，$-2^{31} \le a_i < b_i \le 2^{31}-1$。

样例

输入样例 1

5
-1 3
2 5
4 6
10 12
20 21

输出样例 1

10

提示

$[-1,3) \cup [2,5) \cup [4,6) = [-1,6)$，长度 $7$；再加上 $[10,12)$ 的 $2$ 与 $[20,21)$ 的 $1$，共 $10$。

做法：把所有区间按左端点排序后依次合并，累加每段合并后的长度，复杂度 $O(n\log n)$。