Mental Change

Anjan was feeling low for nearly a couple of months. To improve his condition, he decided to track his mental state using a policy. Based on his activity level and mood, he has assigned a non-negative integer $s_i$ for each day. He calls each values of $s_i$ the satisfaction index (SI) of day $i$.

After generating the satisfaction index value for $n$ days, he went to a psychologist to improve his mental condition. The psychologist was pleased to see his data and gave him an exercise to further analyze his situation. Anjan needs to calculate another integer value called improvement index(II) for each of the n days using the following policy:

1. The II of day $1$ is $1$.

2. For $i >1$, the II of day $i$ is $1$ greater than day $i-1$ if the SI of day $i$ is strictly greater than $s_{i-1}$

3. For $i >1$, if SI of day $i$ less than or equal to the SI of day $i-1$, then the II of day $i$ is $1$.

Despite the work being simple, Anjan felt a lot of stress and decided to take a vacation to Rangamati. He assigned you to calculate the $n$ values for him.

Input

The first line of input contains an integer $n$ ($0 ≤ n ≤ 100$), the number of days Anjan has kept track of his mental states. In the next $n$ lines there will be one integer $s_i$ ( $0 ≤ s_i ≤ 10^9$) each, the satisfaction index of day $i$.

Output

Output $n$ integers in one line, the improvement index of Anjan based on the data he generated.

Sample

Input	Output
3 5 10 9	1 2 1