Quân là một tay cưa gái khét tiếng ở xứ sở Hà Nội Cánh Tay. 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~, Quân chỉ được phép trồng cây có độ cao không quá ~h_i~.

Quân muốn tìm một loại cây có độ cao là số nguyên ~H~ (~H \le h_1~, ~H \le 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 Quân tính xem, độ cao ~H~ nhỏ nhất có thể là bao nhiêu, sao cho nếu Quân chặt đổ cây ở vị trí thứ ~1~ thì cây ở vị trí thứ ~n~ cũng bị đổ theo.

Yêu cầu: Tìm độ cao ~H~ nhỏ nhất thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \le 10^7~).
• Dòng thứ hai chứa ~n~ số nguyên không âm ~h_1, h_2, \dots, h_n~ (~h_i \le 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 1

10 
10 1 2 0 3 4 5 0 2 10

Sample Output 1

2