Có $N$ hoạt động được đề xuất cho một hội trường. Mỗi hoạt động $i$ có thời gian bắt đầu là $\text{start}[i]$ và thời gian kết thúc là $\text{finish}[i]$. Bạn là người quản lý hội trường và muốn chọn ra nhiều hoạt động nhất có thể để tổ chức, với điều kiện là các hoạt động được chọn không được chồng chéo về mặt thời gian. Một hoạt động được xem là bắt đầu ngay khi hoạt động trước đó kết thúc.

Input (Dữ liệu)

• Dòng 1 chứa số nguyên $N$ (số hoạt động)
• Dòng 2 chứa $N$ cặp số nguyên (thời gian bắt đầu và kết thúc) cách nhau một dấu cách.

Output (Kết quả)

• Số lượng hoạt động tối đa có thể tổ chức mà không chồng chéo.

Subtasks (Ràng buộc)

• Subtask 1 ($50\%$): $1 \leq N \leq 10^3$
• Subtask 2 ($50\%$): $1 \leq N \leq 10^5$

Example

6
1 2 
3 4 
0 6 
5 7 
8 9 
5 9

4