19309번 - Gate 21 다국어

You are participating in a ski race. It's rumored that an autograph of Serj Tankian is the grand prize.

Every racer must pass through $n$ gates numbered from 1 to $n$. The $i$-th gate consists of several equivalent checkpoints, which can be considered as points on a plane having coordinates $(i, j)$ for all integers $j$ between $l_i$ and $r_i$, inclusive. It's required to pass through exactly one checkpoint at every gate in increasing order of gate numbers.

Unfortunately, you are very bad at turning on skis. Thus, you would like to prepare a route for yourself which is a straight line passing through a single checkpoint at every gate. How many route options do you have?

The first line of the input contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^9$).

Output a single integer --- the number of valid straight routes you can take.

In the example test case, all possible routes are:

• $(1, 1) \rightarrow (2, 2) \rightarrow (3, 3)$;
• $(1, 2) \rightarrow (2, 2) \rightarrow (3, 2)$;
• $(1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$;
• $(1, 2) \rightarrow (2, 3) \rightarrow (3, 4)$;
• $(1, 3) \rightarrow (2, 2) \rightarrow (3, 1)$;
• $(1, 1) \rightarrow (2, 3) \rightarrow (3, 5)$.