You are given an array of integers. For each integer, write a program to print the length of the longest non-decreasing subsequence ending with that integer.
Two elements can also be equal in the subsequence as it is non-decreasing.

Note: The longest non-decreasing subsequence of a sequence is the longest subsequence in which all the elements are non decreasing, that is, the \(i^{th}\) element of the sequence is greater than or equal to all the elements before it.

Example

Consider N = 4 and A = [3, 4, 1, 6]. You must determine the answer for each index:

For the 1st index, the LIS is [3] and the length is 1.
For the 2nd index, the LIS is [3, 4] and the length is 2.
For the 3rd index, the LIS is [1] and the length is 1.
For the 4th index, the LIS is [3, 4, 6] and the length is 3.

Therefore the answer is [1, 2, 1, 3].

Function description

Complete the LIS function provided in the editor. This function takes the following 2 parameters and returns an array:

N: Represents the size of array A.
A: Represents the elements of the given array.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains an integer \(N\) denoting the number of intergers in the array.
The next line contains \(N\) space-separated integers.

Output format

Print the length of the longest non-decreasing subsequence corresponding to every index.

Constraints
\(1 \le N \le 10^5\\ 1 \le A[i] \le 10^6\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.