Cuộc phiêu lưu trong vườn táo kỳ diệu

Trong một buổi chạy bộ sáng sớm, FullHouse Dev đã tình cờ gặp một vườn táo kỳ lạ. Họ quyết định biến cuộc chạy bộ thành một trò chơi thú vị với những quả táo này. Với tinh thần đồng đội và sự nhanh nhẹn, FullHouse Dev bắt đầu khám phá vườn táo đặc biệt này.

Bài toán

FullHouse Dev đang ở điểm \((1, 1)\) trong một ma trận. Họ có thể di chuyển theo các bước sau:

• Nếu hàng hiện tại có 1 hoặc nhiều quả táo, họ có thể đi đến cuối hàng đó và đi lên.
• Nếu không, họ chỉ có thể đi lên.

Ma trận chứa \(N\) quả táo. Quả táo thứ \(i\) nằm ở điểm \((x_i, y_i)\). FullHouse Dev có thể ăn những quả táo này trong quá trình di chuyển.

Nhiệm vụ của họ là xác định số lượng táo đã được ăn trước mỗi quả táo.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(N\) (1 ≤ N ≤ 10^5) - số lượng quả táo.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\) (1 ≤ x_i, y_i ≤ 10^9) - tọa độ của quả táo thứ \(i\).

OUTPUT FORMAT:

• In ra \(N\) dòng, mỗi dòng chứa một số nguyên - số lượng táo đã được ăn trước quả táo thứ \(i\).

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq x_i, y_i \leq 10^9\)

Ví dụ

INPUT

5
1 4
6 7
2 3
2 5
3 7

OUTPUT

0
4
2
1
3

Giải thích

• Quả táo đầu tiên (1, 4) được ăn trước tiên, nên số táo đã ăn trước đó là 0.
• Quả táo thứ hai (6, 7) được ăn sau cùng, sau khi đã ăn 4 quả táo khác.
• Quả táo thứ ba (2, 3) được ăn sau khi đã ăn 2 quả táo (ở (1, 4) và (2, 5)).
• Quả táo thứ tư (2, 5) được ăn sau khi đã ăn 1 quả táo (ở (1, 4)).
• Quả táo thứ năm (3, 7) được ăn sau khi đã ăn 3 quả táo (ở (1, 4), (2, 3), và (2, 5)).

FullHouse Dev đã hoàn thành cuộc chạy bộ đầy thú vị này, kết hợp giữa việc rèn luyện sức khỏe và giải quyết bài toán thú vị về ăn táo. Họ không chỉ cải thiện thể lực mà còn rèn luyện trí óc, thể hiện tinh thần đồng đội và sự sáng tạo của mình.