Trong một cuộc thi đua chó, ban giám khảo căn cứ vào tốc độ của mỗi chú chó đạt được khi chạy và xếp hạng cho chú chó đó theo một cách đặc biệt: Những chú chó không được chạy cùng một lúc, mà theo trình tự từng chú một. Khi một chú chó bắt đầu chạy, ban giám khảo sẽ căn cứ vào tốc độ của chú chó đó và xếp hạng cho chú chó đó bằng cách so tốc độ của nó với tốc độ của những chú chó đã chạy trước đó.

Ví dụ, giả sử tốc độ của sáu chú chó theo thứ tự chạy như sau:

~(78,24,68,40,39,89)~

Chú chó đầu tiên xếp hạng ~1~ vì trước đó chưa có chú chó nào chạy. Chú chó thứ hai xếp hạng ~2~ vì ~24 < 78~. Chú chó thứ ba cũng xếp hạng ~2~ vì ~24 < 68 < 78~. Chú chó thứ tư xếp hạng ~3~ vì ~24 < 40 < 68 < 78~, chú chó thứ năm xếp hạng ~4~ vì ~24 < 39 < 40 < 68 < 78~ và chú chó cuối cùng xếp hạng nhất với tốc độ ~89~ và ~24 < 39 < 40 < 68 < 78 < 89~. Như vậy trình tự dãy số xếp hạng sẽ là: ~(1,2,2,3,4,1)~. Tóm lại hạng của một chú chó bằng số chó đã chạy nhanh hơn nó cộng thêm ~1~.

Yêu cầu: Có ~n~ chú chó lần lượt bắt đầu chạy, hãy cho biết dãy số biểu diễn giá trị xếp hạng của ~n~ chú chó đó.

Input

Dòng đầu một số nguyên ~n \le 10^5~ cho biết số chú chó tham gia cuộc thi. ~n~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~\le 10^9~ mô tả tốc độ của một chú chó, theo thứ tự mà nó bắt đầu chạy.

Output

Gồm ~n~ dòng: dòng thứ ~i~ ghi số nguyên biểu diễn giá trị xếp hạng của chú chó thứ ~i~ tại thời điểm nó bắt đầu chạy.

Sample Input

6
78
24
68
40
39
89

Sample Output

1
2
2
3
4
1