You can modify the $$$O(N \cdot \log N)$$$ algorithm, run it from right to left and obtain for each $$$i$$$ the smallest value for which there exists an increasing sequence of length $$$i$$$, starting with that value. Consequently you can also obtain the length of the longest increasing sequence that starts at a given index.

Now for the construction, you want to take the smallest value that allows you to make an IS with that starting value. That is the minimum between the numbers where the max length is at least $$$k$$$. Next you want to remove all the values to the left of what you just picked up. You also want to add all the elements to the right of the first element, that have a max_length at least $$$k - 1$$$. Next you remove elements to the left, add new ones from the right, ...

I would suggest you try on a couple small examples, $$$[5, 6, 3, 4, 1, 2]$$$, $$$[1, 2, 3]$$$, $$$[4, 7, 2, 5, 3, 1, 6, 8]$$$.

If you don't understand something then just reply to this comment and I will do my best to explain