LIS2VN - Another Longest Increasing Subsequence Problem

Giới hạn
  • Thời gian: 0.49s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một dãy gồm N cặp số nguyên, tính độ dài của dãy con tăng dài nhất của nó.

Một dãy tăng A 1 ..A n là một dãy con thỏa mãn với mọi i < j , A i < A j .

Một dãy con của một dãy số là một dãy số mà các phần tử của nó có cùng thứ tự với dãy đó, nhưng không cần liên tiếp.

Một cặp số nguyên (x 1 , y 1 ) được gọi là nhỏ hơn (x 2 , y 2 ) nếu x 1 < x 2 và y 1 < y 2 .

Input

Dòng đầu chứa một số nguyên N (2 ≤ N ≤ 100000).

N dòng tiếp theo chứa N cặp số nguyên (x i , y i ) (-10 9 ≤ x i , y i ≤ 10 9 ).

Output

Chứa một số nguyên: độ dài của dãy con dài nhất của dãy đã cho.

Example 

Input:
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6

Output:
3

Bài gốc: http://www.spoj.pl/problems/LIS2/ .

  • Người up: racer
  • Nguồn bài: Jin Bin - SPOJ