Longest Increasing Subsequence Endings

This problem requires you to compute, for each index in a given array, the length of the longest strictly increasing subsequence (LIS) ending at that index. More formally, for each index \(i\) in an array \(arr\) of size \(N\), you should compute \(LIS(i)\) defined as the length of the longest subsequence \(arr[j_1], arr[j_2], \dots, arr[j_k]\) (with \( j_1 < j_2 < \dots < j_k = i \)) such that \(arr[j_1] < arr[j_2] < \dots < arr[j_k]\). This problem tests your ability with dynamic programming and array manipulation.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains an integer \(N\) representing the number of elements in the array.
2. The second line contains \(N\) space-separated integers representing the elements of the array.

You may assume that \(1 \leq N \leq 10^5\) and the array elements are within a reasonable range of integers.

outputFormat

Output a single line to standard output (stdout) containing \(N\) space-separated integers. The \(i^{th}\) integer should represent the length of the longest increasing subsequence ending at index \(i\) of the input array.

## sample

5
1 3 5 3 5

1 2 3 2 3

</p>