[ARC017B] 解像度が低い。

给出长度为N的数组并在其中去找有几个长度为K的上升序列。

[problemUrl]: https://atcoder.jp/contests/arc017/tasks/arc017_2 大変なことになってしまった！！ なんと、我が社の次の決算報告会の発表者に僕が選ばれてしまったのだ！我が社のイメージのためにも、そして社内での僕の地位のためにも、なんとしても好印象を与える発表をせねばならない。 我が社の直近の業績は $ 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 $ 個の連続した部分で、その部分だけ見ると業績が常に上昇しているように見えるものの個数を標準出力に１行で出力せよ。 ``` <pre class="prettyprint linenums"> 10 4 100 300 600 700 800 400 500 800 900 900 ``` ``` <pre class="prettyprint linenums"> 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 $ であることがわかる。 ``` <pre class="prettyprint linenums"> 10 3 10 40 50 80 90 30 20 40 90 95 ``` ``` <pre class="prettyprint linenums"> 5 ``` この場合、常に上昇しているように見える箇所は以下の画像に矢印で示された 5 箇所となる。  ``` <pre class="prettyprint linenums"> 8 4 1 2 3 4 5 6 7 8 ``` ``` <pre class="prettyprint linenums"> 5 ``` 元々の業績が常に上昇しているので、どこをプロジェクターに映しても大丈夫である。 ``` <pre class="prettyprint linenums"> 8 2 100000 90000 50000 30000 10000 4000 200 1 ``` ``` <pre class="prettyprint linenums"> 0 ``` 元々の業績があまりに良くない場合、どこを映しても業績を右肩上がりに見せかけられないことがある。