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.