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 là \(d_{i}\), chiều rộng là \(r_{i}\) (đơ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ì \(d_{i} < d_{j}\) và \(r_{i} < r_{j}\).

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\).

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq {2 \times 10}^{5})\) là số lượng quyển sách.

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo ghi 2 số nguyên dương \(d_{i}\) và \(r_{i}\) (\(1 \leq d_{i},r_{i} \leq 10^{8}\)) tương ứng là chiều dài và chiều rộng của quyển sách thứ \(i\).

Kết quả:

+ Ghi số nguyên \(S\) tìm được.

Ví dụ:

Giới hạn:

• Có 25% số test ứng với 25% số điểm thỏa mãn \(2 \leq n \leq 200\) và \(S \leq 2;\)

• Có 25% số test ứng với 25% số điểm thỏa mãn \(2 \leq n \leq 2 \times 10^{3}\); \(d_{i}
  eq d_{j}\ \)và \(r_{i}
  eq r_{j}\) với mọi cặp \(i
  eq j\); \(1 \leq i,j \leq n;\)

• Có 25% số test ứng với 25% số điểm thỏa mãn \(2 \times 10^{3} < n \leq 2 \times 10^{5}\); \(d_{i}
  eq d_{j}\ \)và \(r_{i}
  eq r_{j}\) với mọi cặp \(i
  eq j\); \(1 \leq i,j \leq n;\)

• Có 25% số test ứng với 25% số điểm còn lại thỏa mãn \(2 \times 10^{3} < n \leq 2 \times 10^{5}\).