Hội trường lớn của Đại học Công nghiệp Hà Nội được các khoa, câu lạc bộ và đoàn thể ưa chuộng để tổ chức sự kiện. Học kỳ này Phòng Quản trị nhận được ~n~ đơn đăng ký; sự kiện thứ ~i~ xin sử dụng hội trường từ thời điểm ~s_i~ đến thời điểm ~e_i~ (các thời điểm được hệ thống đăng ký ghi lại dưới dạng số nguyên), tức là chiếm hội trường trong nửa khoảng thời gian ~[s_i, e_i)~.

Mỗi lúc hội trường chỉ phục vụ được một sự kiện, nên hai sự kiện được chấp thuận không được giao nhau về thời gian. Một sự kiện được phép bắt đầu đúng vào thời điểm sự kiện khác kết thúc: hai sự kiện ~i~ và ~j~ có thể cùng được chấp thuận khi và chỉ khi ~e_i \le s_j~ hoặc ~e_j \le s_i~.

Yêu cầu

Phòng Quản trị muốn chấp thuận càng nhiều sự kiện càng tốt. Hãy tìm số lượng lớn nhất các sự kiện có thể được chấp thuận sao cho không có hai sự kiện nào giao nhau.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~n~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~s_i~ và ~e_i~.

Các sự kiện được cho theo thứ tự bất kỳ và có thể trùng nhau hoàn toàn về thời gian.

Kết quả ra

Ghi ra một số nguyên duy nhất là số sự kiện nhiều nhất có thể chấp thuận.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~0 \le s_i < e_i \le 10^9~.

• Subtask 1 (20% số điểm – test 01–04): ~n \le 15~;
• Subtask 2 (30% số điểm – test 05–10): ~n \le 2000~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

5
1 10
2 4
4 7
6 8
7 9

Kết quả ra mẫu 1

3

Giải thích

Có thể chấp thuận ba sự kiện thứ ~2~, ~3~ và ~5~, chiếm các nửa khoảng ~[2, 4)~, ~[4, 7)~ và ~[7, 9)~: sự kiện ~3~ bắt đầu đúng lúc sự kiện ~2~ kết thúc, sự kiện ~5~ bắt đầu đúng lúc sự kiện ~3~ kết thúc. Không thể chấp thuận ~4~ sự kiện, vì sự kiện ~1~ giao với mọi sự kiện khác, còn trong bốn sự kiện còn lại thì sự kiện ~3~ và sự kiện ~4~ giao nhau.