Super Kth LIS | HackerRank

Given an array of integers (), find all possible increasing subsequences of maximum length, . Then print the lexicographically longest increasing subsequence as a single line of space-separated integers; if there are less than subsequences of length , print .

Two subsequences and are considered to be different if there exists at least one such that .

Input Format

The first line contains space-separated integers, and , respectively.
The second line consists of space-separated integers denoting respectively.

Constraints

Scoring

for of the test data.
for of the test data.

Output Format

Print a single line of space-separated integers denoting the lexicographically longest increasing subsequence; if there are less than subsequences of length , print .

Note: is the length of longest increasing subsequence in the array.

Sample Input 0

5 3
1 3 1 2 5

Sample Output 0

1 3 5

Sample Input 1

5 2
1 3 2 4 5

Sample Output 1

1 3 4 5

Explanation

Sample Case 0:
The longest possible increasing subsequences in lexicographical order are:

Notice that the first and second subsequences appear the same; they are actually both different because the in the first subsequence comes from array element , and the in the second subsequence comes from array element . Because , we print the one () as a single line of space-separated integers.

Sample Case 1:
The longest possible increasing subsequences in lexicographical order are:

Because , we print the one () as a single line of space-separated integers.