#arc0172. [arc017_2]解像度が低い。

[arc017_2]解像度が低い。

问题文

糟糕的事情发生了!!

竟然,我被选为我们公司下次财务报告会的演讲者!为了我们公司的形象,为了我的地位,在公司内部,我必须做出给人留下良好印象的演讲。

我们公司最近的业绩由一个 NN 个数的序列表示。我想要展示这些业绩……但是,不巧的是,我们公司的表现并不怎么好。到底应该怎么办呢……

在困惑之际,我先调查了演讲场所的设备。真是幸运,投影仪的分辨率非常低,屏幕一次只能显示 KK 个数字是极限。如果我能够巧妙地选择出业绩序列中连续的 KK 个数字,岂不是可以让我们公司的业绩看起来像蒸蒸日上呢?

我觉得这是一个绝妙的主意,但是,如果听众问道:“这只是业绩的一部分吧?其他部分也可以展示一下吗?”那就完蛋了。所以,作为一个周密准备的人,我决定提前调查一下,在投影仪上放映时,能够看到业绩一直在上升的部分有多少个。

为了展示我们是一家持续增长的公司,一个值必须真正比前一个值大。也就是说,100,200,300100, 200, 300 这个序列被认为一直在上升,但是 100,200,200100, 200, 200 这个序列不被认为一直在上升。

※这个问题文是虚构的,请确保正确地发布业绩。


输入

输入以以下形式从标准输入中获取:

NN KK A1A_1 A2A_2 : ANA_N

  • 第一行是表示业绩的数列的元素数量 N(1N300,000)N (1 \leq N \leq 300,000),一次投影仪可以显示的数字个数 K(1KN)K (1 \leq K \leq N),以半角空格分隔。
  • 第二行到第 NN 行给出了表示业绩的数列。其中第 ii 行表示第 ii 个业绩的整数 Ai(1Ai300,000)A_i (1 \leq A_i \leq 300,000)

**注意:**本问题需要读取最多 300,000300,000 行的输入。大多数编程语言都没有问题,但是,在 Python 2.x 中,使用 input() 可能会导致超时,因此请改用 int(raw_input()) 来读取整数。


输出

输出一个整数,表示业绩数列中连续的 KK 个部分,在投影仪屏幕上看起来业绩一直在上升的部分的个数。


输入例子1

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

输出例子1

3

从表示业绩的 10 个数中选择连续的 4 个数字,可以得到以下结果:

  • (100,300,600,700)(100, 300, 600, 700) 看起来一直在上升
  • (300,600,700,800)(300, 600, 700, 800) 看起来一直在上升
  • (600,700,800,400)(600, 700, 800, 400) 看起来不一直在上升
  • (700,800,400,500)(700, 800, 400, 500) 看起来不一直在上升
  • (800,400,500,800)(800, 400, 500, 800) 看起来不一直在上升
  • (400,500,800,900)(400, 500, 800, 900) 看起来一直在上升
  • (500,800,900,900)(500, 800, 900, 900) 看起来不一直在上升

因此答案是 3。


输入例子2

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

输出例子2

5

在这种情况下,能够看到看起来一直在上升的地方有 5 个,如下所示:

example2


输入例子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

在业绩本身不太好的情况下,无论将哪部分投射到屏幕上,都无法让业绩看起来像是在持续增长。