Khỉ và chiếc thang trơn (The Monkey and the Oiled Bamboo)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một chiếc thang với $n$ bậc ở các độ cao

Ban đầu bạn đứng ở mặt đất, độ cao $0$, với sức bật nguyên $k$. Mỗi lần chỉ được nhảy từ vị trí hiện tại tới bậc kế tiếp.

• Nếu độ cao cần nhảy lớn hơn sức bật hiện tại, bạn thất bại.
• Nếu đúng bằng sức bật hiện tại, sau cú nhảy sức bật giảm đi $1$.
• Nếu nhỏ hơn sức bật hiện tại, sức bật không đổi.

Hãy tìm giá trị ban đầu nhỏ nhất của $k$ để lên được bậc cao nhất.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $r_1,\ldots,r_n$.

Output

In sức bật nhỏ nhất $k$.

Subtask

• Subtask 1 — 20%: $n\le10$.
• Subtask 2 — 30%: $n\le5000$.
• Subtask 3 — 50%: $1\le n\le10^5$, $1\le r_1<\cdots<r_n\le10^7$.

Ví dụ

Input

5
1 6 7 11 13

Output

5

Giải thích

Với $k=5$, các bước nhảy là $1,5,1,4,2$. Sau bước $5$, sức bật giảm còn $4$; sau bước $4$, giảm còn $3$. Tất cả bước đều thực hiện được.