Thư viện trường học của bạn An có n quyển sách, mỗi quyển sách có dạng hình chữ nhật. Các quyển sách được đánh số thứ tự từ 1 đến n. Quyển sách thứ i (i = 1, 2, …, n) có chiều dài di, chiều rộng ri (đơn vị độ dài). Bạn An muốn chọn một số quyển sách trong n quyển sách để xếp thành một chồng sao cho quyển sách được xếp ở trên có kích thước nhỏ hơn quyển sách được xếp ở dưới, tức là nếu quyển sách i được xếp trên quyển sách j thì di < dj và ri < rj. Yêu cầu: Hãy đưa ra số sách lớn nhất mà bạn An có thể chọn để xếp được chồng sách theo yêu cầu trên. Ta gọi số quyển sách nhiều nhất có thể chọn được là S. Input • Dòng đầu ghi số nguyên dương n (2 ≤ n ≤ 2 × 105) là số lượng quyển sách. • Dòng thứ i của n dòng tiếp theo ghi 2 số nguyên dương di và ri (1 ≤ di, ri ≤ 108) tương ứng là chiều dài và chiều rộng của quyển sách thứ i. Output: ghi số nguyên S tìm được. Input Output Giải thích 2 6 3 5 3 1 Chỉ có thể chọn được 1 quyển sách (quyển 1 hoặc quyển 2) 5 3 2 4 1 10 6 8 4 7 5 3 Chọn được nhiều nhất 3 quyển sách: Có thể chọn quyển 1, 3, 5 Cách xếp theo thứ tự từ trên xuống quyển 1 quyển 5 quyển 3 2 5 4 3 1 2 Chọn được 2 quyển sách: quyển 1 và quyển 2. Cách xếp theo thứ tự từ trên xuống: quyển 2 quyển 1 Giới hạn: • 25% test có 2 ≤ n ≤ 200 và S ≤ 2 • 25% có 2 ≤ n ≤ 2 × 103; di ≠ dj và ri ≠ rj với mọi i ≠ j; 1 ≤ i, j ≤ n • 25% test có 2 × 103 < n ≤ 2 × 105; di ≠ dj và ri ≠ rj với mọi i ≠ j; 1 ≤ i, j ≤ n • 25% test có 2 × 103 < n ≤ 2 × 105