0041 - キーボードが壊れた

問題

はろー！

わたしの悩み事聞いてくれるー？ 最近また学校のキーボードを壊しちゃって・・・。これで 3 個目。先生に、「なんにもしてないよ＞＜」っていってもなぜか渋い顔をして怒られちゃった。よくわかんないよねー。

先生が言うには、わたしの打鍵音の大きさと関係があるみたい。えっとー、パソコンをやってるとだんだんいらいらしてきちゃって、打鍵音が大きくなったりしてるらしいんだよね。

そこで、これ以上キーボードを壊れないように、私にアドバイスしてほしいんだ。具体的にはね、まず、わたしの打鍵音の大きさの情報が時系列順にあって、連続して打鍵音の大きさが K 回大きくなってるところが危ないらしんだよね。君にはその回数を数えてもらって、私の「いらいら度」を測定して欲しいんだー。

例えばね、打鍵音の大きさが {100, 200, 300} だとするよねー。K = 2 のときは、{100, 200} と {200, 300} が大きくなっていて、これだと 2回 になるよ。K = 3 のときは、{100, 200, 300} の 1 回だよね。

入力

N K
T1
T2
：
TN

• 1 行目には、わたしの打鍵音の大きさを表す数列の要素数 N(1 ≦ N ≦ 3 00,000)と K(1 ≦ K ≦ N) が半角空白区切りで与えられる。
• 2 行目には、打鍵音の大きさを表す数列が時系列順に与えられる。このうち i 行目が i 番目の打鍵音の大きさを表す整数 T_i(1 ≦ A_i ≦ 3 00,000) である。

出力

1 行に、打鍵音が連続して K 回大きくなっている箇所の個数を出力せよ。

入力例1

10 4
100
300
600
700
800
400
500
800
900
900

出力例1

3

業績を表す 10 個の数列から、連続する 4 個を抜き出してみると、

• (100, 300, 600, 700) は常に上昇しているように見える
• (300, 600, 700, 800) は常に上昇しているように見える
• (600, 700, 800, 400) は常に上昇しているように見えない
• (700, 800, 400, 500) は常に上昇しているように見えない
• (800, 400, 500, 800) は常に上昇しているように見えない
• (400, 500, 800, 900) は常に上昇しているように見える
• (500, 800, 900, 900) は常に上昇しているように見えない

となるので、答えは 3 であることがわかる。

入力例2

8 4
1
2
3
4
5
6
7
8

出力例2

5

常に打鍵音の大きさは上昇しているので、{1,2,3,4}, {2,3,4,5}, {3,4,5,6}, {4,5,6,7}, {5,6,7,8} で 5 個である。

入力例3

10 3
10
40
50
80
90
30
20
40
90
95

出力例3

5

入力例4

8 2
100000
90000
50000
30000
10000
4000
200
1

出力例4

0

常に打鍵音の大きさは減少しているので、答えは 0 である。