Thuận là một bác tiêu phu lừng danh về tài năng chặt cây của mình. Hôm nay Thuận sẽ trồng và chặt một hàng cây gồm \(n\) cây để lấy gỗ xây nhà mới cho mình, các cây được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ở vị trí thứ \(i\), Thuận chỉ được phép trồng cây có độ cao không quá \(h_{i}\).

Thuận muốn tìm một loại cây có độ cao là số nguyên \(k\) \((k \leq h_{1}, k \leq 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\) (\(i < n\)) bị đổ, nó sẽ làm các cây ở vị trí trong khoảng \([i + 1, min(n, i + k)]\) đổ theo.

Hãy giúp Thuận tính xem, độ cao \(k\) nhỏ nhất có thể là bao nhiêu, sao cho nếu Thuận 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 \leq 10^{7})\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(h_{1}, h_{2}, \ldots, h_{n}\) \((0 \leq h_{i} \leq 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.

Scoring

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

Example

10 
10 1 2 0 3 4 5 0 2 10

2