엇갈리는 승객 쌍

문제

일직선으로 뻗은 지하철 노선이 있다. 오늘 이 노선을 이용한 승객은 N명이며, i번째 승객은 위치 s_i 에서 타서 위치 e_i 에서 내렸다. (s_i < e_i) 승객은 구간 [s_i, e_i] 를 이동한 것으로 본다.\n\n두 승객 a, b 가 다음 조건을 모두 만족하면 이 쌍을 엇갈리는 쌍이라 한다.\n\n- s_a < s_b < e_a < e_b 이다.\n\n즉 두 승객이 함께 탄 구간의 길이가 0보다 크면서, 어느 한쪽의 이동 구간이 다른 쪽에 완전히 포함되지는 않는다. 시작 위치나 끝 위치가 같은 쌍, 한 승객이 내린 위치에서 다른 승객이 타는 쌍은 엇갈리는 쌍이 아니다. 서로 다른 승객 번호의 쌍은 순서를 구분하지 않고 한 번만 센다.\n\n오늘 이용한 승객 중 엇갈리는 쌍이 모두 몇 개인지 구하여라.

입력

첫째 줄에 승객 수 N이 주어진다. (1 ≤ N ≤ 200,000)\n다음 N개의 줄에 i번째 승객의 s_i 와 e_i 가 공백으로 구분되어 주어진다. (1 ≤ s_i < e_i ≤ 10^9, 정수)

출력

엇갈리는 쌍의 개수를 한 줄에 출력한다.

4
1 5
2 6
3 4
4 8

3

3
1 2
1 2
1 2

0

3
1 3
2 4
2 5

2

출처: Devin.KR 자체 제작