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
78246840398978246840398978 \quad 24 \quad 68 \quad 40 \quad 39 \quad 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:
1223411223411 \quad 2 \quad 2 \quad 3 \quad 4 \quad 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:-----
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:-----
Your output should consist of $N$ lines. Line $i$ should be the rank announced when the $i^{th}$ minister enters the hall.

-----Constraints:-----
- $1 \leq N \leq 45000$.
- No two merchants have the same wealth.
- You may also assume that in $30 \%$ of of the inputs $1 \leq N \leq 8000$.

-----Sample Input-----
6
78
24
68
40
39
89

-----Sample Output-----
1
2
2
3
4
1

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "n=int(input())\r\narr=[]\r\nfor i in range(n):\r\n    arr.append(int(input()))\r\n\r\nans=[]\r\nans.append(1)\r\n\r\nfor i in range(1, n):\r\n    val=arr[i]\r\n    for j in range(i-1, -2, -1):\r\n        if(j==-1):\r\n            arr[j+1]=val\r\n            ans.append(1)\r\n            break\r\n\r\n        if(arr[j]<val):\r\n            arr[j+1]=arr[j]\r\n        else:\r\n            arr[j+1]=val\r\n            ans.append(j+2)\r\n            break\r\n        \r\n    #print(arr, val)\r\n\r\nprint(*(ans), sep='\\n')\r\n        "
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13215