Lập lịch


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Toto vừa được bổ nhiệm làm chủ tịch của tổng công ty TNHH_MTV nên có rất nhiều công việc cần giải quyết. Mỗi công việc có một thời điểm bắt đầu và một thời điểm kết thúc mà Toto không thể làm hai việc được cùng lúc tức là chỉ khi việc này chấm dứt hoàn toàn thì mới bắt đầu được việc khác.

Giả sử bạn là Tổng thư ký cho Toto bạn hãy lập lịch cho Toto sao cho số công việc mà Toto có thể làm là nhiều nhất và không xung đột với nhau.

Input

Dòng đầu chứa số lượng công việc \(n (1 \le n \le 10^5)\)

Tiếp theo \(n\) dòng mỗi dòng chứa thời gian bắt đầu và kết thúc của từng công việc \(s_i,f_j (1 \le s_i < f_i \le 10^9)\)

Output

Số công việc được chọn nhiều nhất sao cho các công việc không giao nhau kể cả ở các đầu mút thời gian

Ví dụ

Input

5
4 7
2 8 
3 6
7 9
9 12

Output

2
tichpx

Comments

There are no comments at the moment.