Mây là một tay cưa gái khét tiếng ở xứ sở IUH. Cưa gái nhiều nên đã quá ngán, cậu bèn chuyển qua cưa cây. Hàng cây gồm ~n~ cây, được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ở vị trí thứ ~i~, Mây chỉ được phép trồng cây có độ cao không quá ~h_i.~ Mây muốn tìm một loại cây có độ cao là số nguyên ~H~ (~H≤h_1,H≤h_n~) và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ 1 và thứ ~n~. Nếu cây ở vị trí thứ ~i~ bị đổ, nó sẽ làm các cây ở vị trí trong khoảng ~[i+1,i+H]~ đổ theo.

Hãy giúp Mây tính xem, độ cao ~H~ nhỏ nhất có thể là bao nhiêu, sao cho nếu Mây chặt đổ cây ở vị trí thứ 1 thì cây ở vị trí thứ ~n~ cũng bị đổ theo.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n≤10^7~).
• Dòng thứ hai chứa ~n~ số nguyên không âm ~h_1,h_2,…,h_n~ (~h_i≤n~). Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Output

In ra một số nguyên dương là kết quả của bài toán.

Sample input

10 
10 1 2 0 3 4 5 0 2 10

Sample output

2

Giải thích

Mây trồng cây độ cao ~2~ ở các vị trí ~1,3,5,7,9,10.~

Subtask

• Subtask 1 (20% số điểm): ~n ≤100.~
• Subtask 2 (20% số điểm): ~n ≤1000.~
• Subtask 3 (20% số điểm): ~n≤10^5.~
• Subtask 4 (20% số điểm): ~n≤10^6.~
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.