The key to solving this task is noticing that in any sequence of length ~N~ there has to be a monotone subsequence of length at least ~\sqrt N~. Why is that so?

Let's try and prove it.

Let's imagine that we have a set of stacks stacked from left to right, with the feature that the numbers are ascending as we are getting to the top of the stack. Now we do the following algorithm: go through the numbers in the array from left to right, pushing each number to the top of the first stack that we can from the left so that it still holds that the numbers on all stacks are ascending.

Let's observe the first case: after this algorithm, we have less than or equal to ~\sqrt N~ nonempty stacks. In that case, there has to be a stack with more than or equal to ~\sqrt N~ numbers on it, and it clearly follows that the number of total numbers on stacks is precisely ~N~. In this case, we have shown that at least an ascending subsequence is of the length ~\sqrt N~.

Let's now observe the second case: after this algorithm, we have more than ~\sqrt N~ nonempty stacks. Let's observe the element on top of each stack. We notice that the numbers on top of the stacks are descending, looking from left to right. In the case that they are not descending, it would mean that we hadn't complied to our construction features during the execution of this algorithm, because we pushed to the top of the first stack that we could so that the next number is larger than the last on the stack, and it is the first stack that we could push to. Having that in mind, we have a descending subsequence of length at least ~\sqrt N~ that consists of numbers on top of all stacks.

We have completed the proof. There is always a monotone subsequence of length at least ~\sqrt N~.

After this, it is fairly simple to see that the next construction gives a monotone sequence of required length ~K~, assuming that ~K \ge \sqrt N~, otherwise such a sequence doesn't exist.

Let the sequence be in the form of ~[n-k+1, n], [n-2k+1, n-k], [n-3k+1, n-2k], \dots~.

Each subsequence of length ~K~ has an ascending subsequence of length ~K~, and because there are ~\le K~ such sequences, because ~K \ge \sqrt N~, a descending sequence of length larger than ~K~ does not exist.