Tại câu lạc bộ võ Karate, cả nam lẫn nữ có tất cả \(n\) võ sinh được xếp thành một hàng đánh số từ 1 đến \(n\). Võ sinh thứ \(i\) có năng lực chiến đấu là một số nguyên \(a_{i}\). Huấn luyện viên muốn cho các võ sinh của mình đấu giao hữu với nhau theo nguyên tắc như sau:

+ Chỉ thi đấu với nhau khi cùng giới tính.

+ Mỗi võ sinh sẽ được đấu với các võ sinh đứng trước họ từ gần đến xa, đến khi nào thua trận thì thôi. (Võ sinh thứ \(i\) thắng võ sinh thứ \(j\) nếu \(j < i\) và \(a_{j} < a_{i}\)).

Yêu cầu: Hãy cho biết, mỗi võ sinh thắng bao nhiêu võ sinh khác theo nguyên tắc trên.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(n\ (n\ \leq \ 10^{6})\) là số lượng võ sinh.

+ \(n\) dòng sau, mỗi dòng chứa hai số nguyên, dòng thứ \(i + 1\) chứa số nguyên \(a_{i}\) và \(b_{i}\), trong đó \(a_{i}\) là năng lực chiến đấu, \(b_{i}\) là giới tính của võ sinh thứ \(i\ (1 \leq \ a_{i}\ \leq \ 10^{9},\ b_{i}\ \in \ \{ 0,1\})\).

Kết quả:

+ Ghi một dòng duy nhất gồm \(n\) số nguyên, số thứ \(i\) là số lượng võ sinh mà võ sinh thứ \(i\) đấu thắng.

Ví dụ:

Ràng buộc:

+ 40% số test với \(n\ \leq \ 10^{3}\)

+ 60% số test với \(n\ \leq \ 10^{6}\)