| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 2048 MB | 4 | 4 | 4 | 100.000% |
Due to their privileged location and favorable terrain, only frontal walls were usually necessary to protect medieval cities in Minas Gerais. Even today, it is possible to find traces of these constructions when admiring the beautiful horizon of the region.
Each of these walls was composed of a number of consecutive segments, each with an initial height measured in units, corresponding to the number of blocks used to build it.
From time to time, the builders reinforced the walls by choosing a segment and stacking extra blocks in a staircase pattern: the chosen segment received $K$ additional blocks, the previous one $K − 1,ドル and so on until only 1ドル$ block was added or there were no more segments to the left.
The defense was considered as strong as its lowest segment.
Given the initial description of a wall, your objective is to determine the largest possible minimum height after applying a single reinforcement.
The first line contains two integers $N$ (1ドル ≤ N ≤ 10^5$), the number of wall segments, and $K$ (1ドル ≤ K ≤ N$), the number of blocks added to the chosen segment.
The second line contains $N$ integers $x_1, x_2, \dots , x_N$ (1ドル ≤ x_i ≤ 10^9$), representing the initial heights of the segments.
Your program should print a single line, containing a single integer: the largest possible minimum height of the wall after a single reinforcement.
5 5 5 4 3 2 1
6
6 1 3 3 1 3 3 3
2
5 5 3 4 7 8 7
7
If we reinforce the first segment, the wall now has heights $[8, 4, 7, 8, 7]$. The lowest segment in this case has height 4ドル$.
Reinforcing the last segment, we get $[4, 6, 10, 12, 12],ドル where the minimum is 4ドル$.
Of all the options, the best choice is to reinforce the second segment, resulting in $[7, 9, 7, 8, 7],ドル where the minimum is 7ドル$.
Therefore, the greatest possible minimum height is 7ドル$.