Hai đoạn không giao nhau

Time limit: 1.0 s
Memory limit: 256 MB
Points: 3,500
AC rate: 27.7%
Solvers: 20

Cho $N$ ~N~ đoạn số nguyên, các đoạn được đánh số từ $1$ ~1~ đến $N$ ~N~. Đếm số cặp $(i,j)$ ~(i,j)~ $(1 \le i < j \le N)$ ~(1 \le i < j \le N)~ thỏa mãn đoạn thứ $i$ ~i~ và đoạn thứ $j$ ~j~ là hai đoạn không giao nhau.

Hai đoạn $[a,b]$ ~[a,b]~ và $[c,d]$ ~[c,d]~ được gọi là không giao nhau khi và chỉ khi $b < c$ ~b < c~ hoặc $d < a$ ~d < a~.

Input

Dòng đầu tiên chứa số nguyên $N$ ~N~ $(2 \le N \le 5.10^5)$ ~(2 \le N \le 5.10^5)~.
$N$ ~N~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa hai số nguyên $L_i$ ~L_i~ và $R_i$ ~R_i~ mô tả đoạn $[L_i,R_i]$ ~[L_i,R_i]~ $(0 \le L_i \le R_i \le 5.10^5)$ ~(0 \le L_i \le R_i \le 5.10^5)~.

Output

In ra số lượng cặp $(i,j)$ ~(i,j)~ thỏa mãn.

Samples

Sample Input 1

Sample Output 1

Sample Input 2

2
1 3
3 5

Sample Output 2

Scoring

Subtask $1$ ~1~ với $1000$ ~1000~ điểm: $N \le 3000$ ~N \le 3000~
Subtask $2$ ~2~ với $1250$ ~1250~ điểm: $|L_i-R_i| \le 5$ ~|L_i-R_i| \le 5~ $\forall$ ~\forall~ $1 \le i \le N$ ~1 \le i \le N~
Subtask $3$ ~3~ với $1250$ ~1250~ điểm: Không có ràng buộc gì thêm

Clarification

Ở ví dụ đầu tiên, các cặp $(i,j)$ ~(i,j)~ thỏa mãn bao gồm:

$i=1,j=4$ ~i=1,j=4~: Đoạn $[1,4]$ ~[1,4]~ và đoạn $[6,9]$ ~[6,9]~ không giao nhau.
$i=2,j=4$ ~i=2,j=4~: Đoạn $[2,3]$ ~[2,3]~ và đoạn $[6,9]$ ~[6,9]~ không giao nhau.

Comments

You need to sign in to write comments, reply and vote.