Longest Increasing Subsequence Endings

Given an array of integers, modify each element so that it represents the length of the longest strictly increasing subsequence ending at that element. In other words, for an array (a), compute an array (dp) where

[ dp[i] = \max_{0 \le j < i \text{ and } a[i] > a[j]} {dp[j] + 1} ]

with the base case (dp[i] = 1) for every index (i). The answer should be output as a space-separated sequence of numbers.

inputFormat

The input begins with a single integer (n) (where (1 \le n \le 10^5)) that denotes the number of elements in the array. The next line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single line containing (n) space-separated integers. The (i)-th integer should be the length of the longest strictly increasing subsequence ending at the (i)-th element of the input array.## sample

6
10 22 9 33 21 50

1 2 1 3 2 4