Thanh kiếm (Swords)

Nguồn: Sở Giáo dục và Đào tạo Hà Nội — Đề chính thức kỳ thi chọn học sinh giỏi thành phố và chọn đội tuyển học sinh giỏi dự thi Olympic quốc gia các môn văn hóa, lớp 12 THPT, năm học 2026–2027 (Bảng A)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trong một trò chơi nhập vai, người chơi thu thập được $N$ thanh kiếm được đánh số từ $1$ tới $N$. Mỗi thanh kiếm $i$ có chỉ số tấn công $a_i$ và chỉ số phòng thủ $b_i$.

Một thanh kiếm $i$ bị coi là vô dụng (bị thống trị hoàn toàn) nếu tồn tại một thanh kiếm $j$ khác, $j\ne i$, sao cho đồng thời:

và

Ngược lại, nếu không tồn tại bất kỳ thanh kiếm $j$ nào thỏa mãn cả hai điều kiện trên thì thanh kiếm $i$ được coi là hữu dụng.

Biết rằng không có hai thanh kiếm nào trùng nhau ở cả hai chỉ số, tức là không tồn tại $i\ne j$ sao cho $a_i=a_j$ và $b_i=b_j$.

Hãy đếm số lượng thanh kiếm hữu dụng.

Input

• Dòng đầu tiên chứa một số nguyên dương $N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $a_i, b_i$, lần lượt là chỉ số tấn công và chỉ số phòng thủ của thanh kiếm $i$.

Output

In ra một số nguyên là số lượng thanh kiếm hữu dụng.

Subtask

• Subtask 1 (80 điểm): $1\le N\le 1000$; $1\le a_i,b_i\le 10^9$.
• Subtask 2 (20 điểm): $1\le N\le 10^5$; $1\le a_i,b_i\le 10^9$; không có ràng buộc thêm.

Trong mọi Subtask, không có hai thanh kiếm nào trùng nhau ở cả hai chỉ số.

Ví dụ

Input

4
3 2
2 4
4 1
1 3

Output

3

Giải thích

Các thanh kiếm $1$, $2$ và $3$ là hữu dụng. Thanh kiếm $4$ có cặp chỉ số $(1,3)$ và bị thanh kiếm $2$ có cặp chỉ số $(2,4)$ thống trị hoàn toàn vì $2\ge1$ và $4\ge3$, nên thanh kiếm $4$ là vô dụng.