← 返回题目列表

AtCoder · dwacon2018_final_b

B. 逐渐强大

中文机器翻译题面 查看原题

配点 : 800 点

問題文

Nico Nico的吉祥物TV-chan将于明天开始上线。 N 我们将进行几天的直播。 N TV酱可以在白天的任何一天暂停直播。

TV-chan直播时能发出的音量是按天决定的。 i 当天 将以 v_i 的音量播放。

TV酱今年的目标是“变得更强”。于是,TV酱决定选一天进行直播,这样声音会比前一天更大。然而,要保持坚强是很困难的,所以 我们决定违反此规则并直播最多 K 次是可以的。第一次直播的音量可以随意。

在这个规则下,TV-chan可以直播多少次?

制約

  • 1 \leq N \leq 10^5
  • 0 \leq K \leq 100
  • 0 \leq v_i \leq 10^9

入力

输入是按以下格式从标准输入给出的。

N K
v_1 ... v_N

出力

将您的答案打印在一行上。

入力例 1

8 2
4 1 6 2 8 5 7 3

出力例 1

6

例如 您可以在 1, 2, 4, 6, 7, 8 日进行直播。此时的力量是 4, 1, 2, 5, 7, 3 并且比前一天更强,除了第2天和第8天的两次。

入力例 2

3 0
1 1 1

出力例 2

1

可以以与前一天相同的强度进行广播。 请注意,您只能执行 K 次。

入力例 3

5 2
5 1 3 2 4

出力例 3

5