Surge

Time limit1sMemory limit512 MB

Summary

Given N surge dates and a target K, find the smallest integer peak price X such that selling one coin each day from the first surge until the price hits zero yields at least K.

Level: Medium7 of 10
Topics: Binary search, Math, Prefix sum, Greedy
Solved: No attempts yet

Problem

Hyeoseok, the issuer of the Yeongil coin, holds infinitely many Yeongil coins and can adjust their price however he likes.

One day, needing cash, Hyeoseok wants to sell Yeongil coins and cash out at least K won.

Hyeoseok plans to surge the coin's price on N dates he has chosen, then sell one coin every day starting from the first day the price rises. On each chosen date the Yeongil coin rises to X won, and afterward its price drops by 1 won per day until it reaches 0 won. Since a price that rises too much could draw suspicion, he wants to cash out with the smallest possible surge.

Help Hyeoseok find the smallest integer X that lets him cash out at least K won.

Input

The first line gives two integers N and K. (1 ≤ N ≤ 106, 1 ≤ K ≤ 1018)

The second line gives the N dates A1, ..., An that Hyeoseok chose, in increasing order. The coin's price rises Ai days from now. (1 ≤ Ai ≤ 109)

Output

Print the smallest integer X that lets him cash out at least K won by the time the coin's price reaches 0 after the last price surge.

Examples2

Example 1
Input
```
3 10
1 2 4
```
Expected output
```
3
```
Example 2
Input
```
5 5
1 10 100 1000 10000
```
Expected output
```
1
```