#2341. 希蒙的序列最值

希蒙的序列最值

希蒙的序列最值

题目背景

希蒙累了,他现在只想做一些简单的题目,比如在一个序列中找最大的数!

但这也太简单了,希蒙想给这个问题增加一点点趣味性,于是他给了自己kk次机会,给序列中的一些数加一。

为了增加一点难度,他每次操作能选择的数必须满足下述条件:

1<=i<=n1ai<=ai+11<=i<=n-1\wedge a_i<=a_{i+1}

则希蒙可以给aia_i加一。

经过操作以后,输出序列中的最大值最大为多少。

题目描述

给定一个序列a1,a2,,ana_1,a_2,\cdots,a_n,你一共可以进行kk次操作。

每次操作如下:

选择一个下标1<=i<=n11<=i<=n-1,且满足ai<=ai+1a_i<=a_{i+1},使ai=ai+1a_i=a_i+1

求经过操作后序列最大值最大为多少。

输入格式

第一行两个整数n,kn,k,表示序列长度与操作次数。

第二行nn个整数aia_i,表示序列。

输出格式

你一共需要输出一个整数,表示操作后的序列的最大的最大值。

样例 #1

样例输入 #1

3 4
1 3 3

样例输出 #1

4

提示

数据范围:

对于30%的数据,我们保证1<=n,k<=201<=n,k<=20

对于100%的数据,我们保证1<=n<=103,1<=ai,k<=1081<=n<=10^3,1<=a_i,k<=10^8