Indian National Olympiad in Informatics

Related:

Online Programming Contest, 1-2 January, 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 2: What is the Rank?, (K Narayan Kumar, CMI)

This is one more story about our old friend, the Despotic King. Once every year, it was customary for the king to give audience to the rich merchants of his country in a large hall. On that day, the merchants were ushered in to meet the king one by one and after paying their respects to the king they were seated in the auditorium.

It was the job of the minister to introduce each merchant, as he arrived, to the others in the hall. He would announce his name and his wealth. However, our quirky king demanded that in addition, he should also announce the rank of the merchant among all those in the hall (at the time of his arrival) in terms of his wealth.

For example, let us suppose that the wealth of the 6 merchants who met the king (in the order in which they arrived) is given by the sequence

 78  24  68  40  39  89

Then, clearly the first merchant is the richest in the hall when he enters it (since there are no others in the hall) and so his rank is 1. Since 24 < 78 the rank of the second merchant when he enters the hall is 2. The rank of the third merchant is also 2 since 24 < 68 < 78. The rank of the fourth merchant is 3 since 24 < 40 < 68 < 78, the rank of the fifth merchant is 4 since 24 < 39 < 40 < 68 < 78 and finally the rank of the sixth merchant is 1 since 24 < 39 < 40 < 68 < 78 < 89. The sequence of ranks announced by the minister would thus be:

 1  2  2  3  4  1

Your task is to write a program that takes as input a sequence of distinct positive integers indicating the wealth of the merchants in the order in which they visit the king and outputs the sequence of ranks announced by the minister.

Input format

The first line contains a single integer N indicating the number of merchants. The next N lines (line 2,...,N+1) describe the wealth of these N merchants. Line i+1 contains a single positive integer indicating the wealth of the i^th merchant to enter the hall.

Output format

Your output should consist of N lines. Line i should be the rank announced when the i^th minister enters the hall.

Test Data:

You may assume N ≤ 45000 and that no two merchants have the same wealth. Further you may also assume that in 30% of of the inputs N ≤ 8000.

Example:

Here are the inputs and outputs corresponding to the example discussed above.

Sample Input

Sample Output