Contest Duration: - (local time) (100 minutes) Back to Home
D - Intersecting Intervals /

Time Limit: 3 sec / Memory Limit: 1024 MB

### 問題文

N 個の実数の区間が与えられます。i\,(1 \leq i \leq N) 番目の区間は [l_i,r_i] です。i 番目の区間と j 番目の区間が共通部分を持つような組 (i,j)\,(1\leq i < j \leq N) の個数を求めてください。

### 制約

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• 入力はすべて整数

### 入力

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N


### 入力例 1

3
1 5
7 8
3 7


### 出力例 1

2


### 入力例 2

3
3 4
2 5
1 6


### 出力例 2

3


### 入力例 3

2
1 2
3 4


### 出力例 3

0


Score : 400 points

### Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

### Constraints

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• All input values are integers.

### Input

The input is given from Standard Input in the following format:

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N


### Sample Input 1

3
1 5
7 8
3 7


### Sample Output 1

2


The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

### Sample Input 2

3
3 4
2 5
1 6


### Sample Output 2

3


### Sample Input 3

2
1 2
3 4


### Sample Output 3

0