AtCoder Regular Contest 017

B - 解像度が低い。


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

大変なことになってしまった!!

なんと、我が社の次の決算報告会の発表者に僕が選ばれてしまったのだ!我が社のイメージのためにも、そして社内での僕の地位のためにも、なんとしても好印象を与える発表をせねばならない。

我が社の直近の業績は 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()) を使うこと。

出力

業績を表す数列のうち、プロジェクターで画面に映せるような K 個の連続した部分で、その部分だけ見ると業績が常に上昇しているように見えるものの個数を標準出力に1行で出力せよ。

入力例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

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

出力例2

5
この場合、常に上昇しているように見える箇所は以下の画像に矢印で示された 5 箇所となる。

入力例3

8 4
1
2
3
4
5
6
7
8

出力例3

5
元々の業績が常に上昇しているので、どこをプロジェクターに映しても大丈夫である。

入力例4

8 2
100000
90000
50000
30000
10000
4000
200
1

出力例4

0
元々の業績があまりに良くない場合、どこを映しても業績を右肩上がりに見せかけられないことがある。


Submit提出する