Longest Increasing Subsequence Ending at Each Element

Given an array of integers, for each element, compute the length of the longest strictly increasing subsequence (LIS) that ends at that element.

More formally, for an array \(a_1, a_2, \ldots, a_n\), you are to compute an array \(L_1, L_2, \ldots, L_n\) where \[ L_i = 1 + \max_{1 \le j < i \; \text{and} \; a_j < a_i} L_j, \] with the convention that if there is no valid \(j\), then \(L_i = 1\). This is the classical dynamic programming problem of finding increasing subsequences, but here you must output the length for each position separately.

Example:
For the input array [3, 10, 2, 1, 20], the result is [1, 2, 1, 1, 3].

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(0 \le n \le 10^5\)) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single line containing \(n\) space-separated integers where the \(i\)-th integer is the length of the longest strictly increasing subsequence ending at the \(i\)-th element of the array.

## sample

5
3 10 2 1 20

1 2 1 1 3

</p>