Dễ
Chuỗi điểm không giảm 2
Trên mặt phẳng có \(N\) điểm được liệt kê theo một thứ tự cố định, điểm thứ \(i\) có toạ độ nguyên \((a_i, b_i)\). Ta muốn chọn ra một số điểm, giữ nguyên thứ tự xuất hiện của chúng, sao cho khi đi từ điểm chọn này sang điểm chọn kế tiếp thì cả hoành độ lẫn tung độ đều không giảm.
Nói cách khác, cần tìm dãy chỉ số \(i_1 < i_2 < \dots < i_k\) sao cho với mọi \(t\) ta có \(a_{i_t} \le a_{i_{t+1}}\) và \(b_{i_t} \le b_{i_{t+1}}\). Hãy tìm giá trị \(k\) lớn nhất.
Input
- Dòng đầu tiên chứa số nguyên dương \(N\).
- \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).
Output
In ra một số nguyên duy nhất là độ dài lớn nhất \(k\) của dãy điểm chọn được.
Constraints
- \(1 \le N \le 10^5\)
- \(0 \le a_i, b_i \le 10^9\)
Sample Input
7
40 400
20 600
50 400
50 700
10 900
80 800
50 700
Sample Output
4
Explanation
Chọn các điểm thứ 1, 3, 4, 6: \((40,400) \to (50,400) \to (50,700) \to (80,800)\). Không tồn tại dãy dài hơn.