/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
大変なことになってしまった！！
なんと、我が社の次の決算報告会の発表者に僕が選ばれてしまったのだ！我が社のイメージのためにも、そして社内での僕の地位のためにも、なんとしても好印象を与える発表をせねばならない。
我が社の直近の業績は N 個の数からなる数列で表される。これを発表したいところだけれど……、あいにく、我が社の業績はそこまで良いとは言えないのが実情だ。一体どうすればいいんだろうか……。
途方に暮れた僕は、とりあえず発表会場の設備を調査した。なんと、これが僕の生まれ持った強運か、プロジェクターの解像度がとても低く、画面には一度に K 個の数を表示するのが限界であることがわかった。業績の数列のうちの連続する K 個をうまく選べれば、我が社の業績がうなぎのぼりであるように見せかけられるのではないだろうか？
これは最高のアイデアだと思ったが、聴衆から「それって業績の一部ですよね？他の部分も見せて頂けませんか？」と言われたらジ・エンドだ。そこで用意周到な僕は、業績の数列のうち、プロジェクターで映したときに業績が常に上昇しているように見せられるような箇所がいくつあるのか、事前に調べておくことにした。
常に成長を続ける企業であるとアピールするためには、ある値はその前の値より真に大きくなくてはいけない。つまり 100, 200, 300 という列は常に上昇していると考えるが、 100, 200, 200 という列は常に上昇しているとは考えない。
※この問題文はフィクションです。業績はきちんと発表しましょう。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 : A_N
- 1 行目には、業績を表す数列の要素数 N (1 \leq N \leq 300,000)、プロジェクターで一度に表示できる数の個数 K (1 \leq K \leq N) が半角空白区切りで与えられる。
- 2 行目から N 行では、業績を表す数列が与えられる。このうち i 行目が i 番目の業績を表す整数 A_i (1 \leq A_i \leq 300,000) である。
注意: この問題では最大で 300,000 行ほどの入力を読み込む必要がある。ほとんどの言語では問題ないが、Python 2.x で input() を使うと時間制限に間に合わないおそれがあるので、かわりに整数を読み込む際には int(raw_input()) を使うこと。
出力
入力例１
10 4 100 300 600 700 800 400 500 800 900 900
出力例１
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) は常に上昇しているように見えない
入力例２
10 3 10 40 50 80 90 30 20 40 90 95
出力例２
5この場合、常に上昇しているように見える箇所は以下の画像に矢印で示された 5 箇所となる。
入力例３
8 4 1 2 3 4 5 6 7 8
出力例３
5元々の業績が常に上昇しているので、どこをプロジェクターに映しても大丈夫である。
入力例４
8 2 100000 90000 50000 30000 10000 4000 200 1
出力例４
0元々の業績があまりに良くない場合、どこを映しても業績を右肩上がりに見せかけられないことがある。