当前没有测试数据。

题目描述

Given an array A of length $10^9$containing only 1 and -1. The number of 1 is not more than $10^7$. Please count how many pairs of (l, r) satisfy $\sum\limits_{i=l}^r A_i > 0$ and $0 \leq l \leq r < 10^9$

输入格式

The first line of input contains an integers N indicating how many segments of A is 1. Following N lines each contains two space-separated integers $l_i, r_i$ indicating that $A_j$ is 1 for $l_i \leq j \leq r_i$

输出格式

Output one line containing an integer representing the answer.

样例

样例输入 1

1
0 1

样例输出 1

4

样例输入 2

1
1 2

样例输出 2

5

样例输入 3

2
0 1
3 4

样例输出 3

16

数据范围与提示

$0<n≤106$

$l_i \leq r_i$

$r_i + 1 < l_{i+1}$ for $0 \leq i < n - 1$

$0 \leq l_0$

$r_{n-1} < 10^9$

$\sum (r_i - l_i + 1) \leq 10^7$