전설의 쌍검 용사

시간 제한2초메모리 제한512 MB

요약

n개의 (A, B, C) 삼중항이 주어질 때, 각 삼중항의 A를 포함하고 [B, C] 구간 안의 값을 하나 이상 포함하도록 정수 집합의 최소 크기를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 구간, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

남규나라의 공주 Acka가 마왕에게 납치당했다. 왕 zych는 전설의 쌍검 용사 nein에게 공주를 구해 달라고 부탁했다. nein은 길이가 서로 다른 검을 여러 자루 들고 다니며, 적과 싸울 때는 그 중 두 자루를 골라 한 손에 하나씩 들고 싸운다.

정보부가 건넨 자료에 따르면, 적 $i$ 는 오른손에 길이가 정확히 $A_i$ 인 검을 들고 왼손에 길이가 $B_i$ 이상 $C_i$ 이하인 검을 들면 이길 수 있다.

nein이 챙겨 갈 검의 길이 집합을 $L$ 이라 하자. 같은 길이의 검은 한 자루만 챙긴다. 적 $i$ 를 이기려면 $L$ 에 $A_i$ 가 들어 있어야 하고, 동시에 $B_i \le x \le C_i$ 를 만족하는 $x$ 가 $L$ 에 하나 이상 들어 있어야 한다. 이때 $x$ 는 $A_i$ 와 같아도 된다.

모든 길이의 검을 다 챙기면 너무 무겁다. 모든 적을 이길 수 있는 $L$ 중에서 원소가 가장 적은 것을 찾아 그 원소 개수를 출력하여라. 검의 길이는 양의 정수다.

입력

첫째 줄에 마왕성의 적 수 $n$ 이 주어진다. ( $1 \le n \le 100000$ )

다음 $n$ 개 줄에 각 적을 쓰러뜨리기 위한 세 정수 $A$ , $B$ , $C$ 가 공백으로 구분되어 주어진다. ( $1 \le A \le 1000000$ , $1 \le B \le C \le 1000000$ )

출력

마왕성의 적을 모두 쓰러뜨릴 수 있는 검의 최소 개수를 한 줄에 출력한다.

예제2

예제 1
입력
```
3
3 5 10
6 11 15
3 13 15
```
예상 출력
```
3
```
예제 2
입력
```
4
1 10 20
3 50 60
2 30 40
4 70 80
```
예상 출력
```
8
```