409493: GYM103584 F Giant Sequoia

Alfred, an avid botanist and lumberjack, while traveling across the state of California, has come across an absolutely humongous giant sequoia tree. Being the botanist that he is, Alfred would like to examine this fascinating giant sequoia tree in great depth. More specifically, he would like to observe its branches.

Each of the $$$n$$$ branches of the giant sequoia tree has a specific length associated with it, and certain branches are longer than others. Because of this, Alfred was inspired to solve a certain problem, though his skills in computing are quite limited, and he has come to you for help!

Alfred would like to figure out the longest strictly-increasing consecutive sub-array (a sub-array such that $$$a_{i+1} > a_i$$$ for each $$$i$$$ except the last in the sub-array) of the giant sequoia tree branches. However, he is torn between his love for botany and his duties as a lumberjack. He can either choose to leave the tree alone and compute the answer directly, or he can chop off a consecutive sub-array of size exactly $$$k$$$ from the giant sequoia tree before running his computations. More formally, Alfred can choose some index $$$i$$$ such that $$$i + k - 1 \leq n$$$ and then remove the branches at indices $$$i, i + 1, i + 2, \dots, i + k - 1$$$. Since he doesn't have all that much energy after hiking all day, he can only perform this action a maximum of one time.

Given his choices, can you help Alfred find the longest strictly-increasing consecutive sub-array within the giant sequoia tree after at most one chop of size $$$k$$$?

The first line of input will contain a two space-separated integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$), the number of branches of the giant sequoia tree and the number of possible branch removals, respectively.

The second line of input will contain $$$n$$$ space separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$ for $$$1 \leq i \leq n$$$). The $$$i$$$-th integer on the second line represents the length of the $$$i$$$-th branch of the giant sequoia tree starting at the lowest branch.

The output should consist of a single integer $$$x$$$, where $$$x$$$ represents the longest strictly-increasing sub-array of branches after either $$$0$$$ or $$$k$$$ consecutive branch removals.

3 2
1 2 3

3

6 2
1 2 4 3 5 6

4

Alfred can choose to remove either $$$0$$$ or $$$k$$$ consecutive branches from the giant sequoia tree. Actions which are strictly disallowed are removing $$$x$$$ branches where $$$x \not\in \{0, k\}$$$ and/or removing a set of branches which are non-contiguous.