B - だんだん強く /

Time Limit: 5.252 sec / Memory Limit: 525.252 MB

配点 : 800

問題文

ニコニコのマスコットキャラクターであるニコニコテレビちゃんは、明日から N 日間に渡って生放送をすることになりました。 N 日間のうち、テレビちゃんは任意の日に生放送を休むことができます。

生放送をするときにテレビちゃんが出せる音量は日によって決まっていて、 i 日目には v_i の音量で放送します。

テレビちゃんの今年の目標は「だんだん強く」です。なので、テレビちゃんは直前に行ったものよりも大きな音量で放送するように、生放送をする日を選ぶことにしました。ただし、強くし続けるのは大変なので、最大 K 回までこのルールに反して生放送を行う日があってもいいことにしました。最初に行う生放送の音量はなんでも構いません。

このルールのもとで、テレビちゃんは最大何回生放送できるでしょうか?

制約

  • 1 \leq N \leq 10^5
  • 0 \leq K \leq 100
  • 0 \leq v_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N K
v_1 ... v_N

出力

答えを一行に出力せよ。

入力例 1

8 2
4 1 6 2 8 5 7 3

出力例 1

6

たとえば 1, 2, 4, 6, 7, 8 日目に生放送を行うことができます。このとき強さは 4, 1, 2, 5, 7, 3 となって、2 日目と 8 日目の 2 回を除いて直前の日より強くなっています。

入力例 2

3 0
1 1 1

出力例 2

1

直前の日と同じ強さで放送することもたかだか K 回しかできないことに注意してください。

入力例 3

5 2
5 1 3 2 4

出力例 3

5