Doremon truyền năng lượng

Doremon đang du hành vũ trụ thì phát hiện có \(n\) trạm không gian, giả sử các trạm được đánh số từ \(1\) đến \(n\). Trạm thứ \(i\) có khả năng tiếp nhận năng lượng tối đa là \(a_i\) (đơn vị năng lượng).

Doremon có khả năng truyền năng lượng trong phạm vi hoạt động \(K\) (\(K \ge 0\)). Doremon sẽ chỉ truyền được năng lượng giữa các trạm có thể chịu được mức năng lượng \(K\) (\(a_i \ge K\)).

Ban đầu, Doremon nạp năng lượng cho trạm \(1\). Một trạm sau khi nhận được năng lượng có thể truyền tiếp cho các trạm bên phải trong phạm vi \(K\) (tức là các trạm có chỉ số trong đoạn \([i+1, i+K]\)), nếu các trạm đó có thể nhận được năng lượng ở mức \(K\).

Yêu cầu: Giúp Doremon tìm giá trị nhỏ nhất của \(K\) sao cho năng lượng có thể truyền được từ trạm \(1\) đến trạm \(n\).

Input

Dữ liệu vào có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^7\)).

• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le n\)).

Dữ liệu vào đảm bảo luôn tồn tại ít nhất một giá trị \(K\) thỏa mãn yêu cầu.

Ràng buộc:

• Có \(20\%\) số điểm tương ứng với \(n \le 100\).

• Có \(20\%\) số điểm tương ứng với \(n \le 1000\).

• Có \(20\%\) số điểm tương ứng với \(n \le 10^5\).

• Có \(20\%\) số điểm tương ứng với \(n \le 10^6\).

• Có \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Output

In ra một số nguyên dương duy nhất là giá trị nhỏ nhất của \(K\) sao cho năng lượng có thể truyền từ trạm \(1\) đến trạm \(n\).

Example

Input:

9
9 8 8 0 0 8 0 0 9

Output:

3

Note

Với \(K = 3\), chỉ những trạm có \(a_i \ge 3\) mới được tham gia truyền năng lượng: \(\{1, 2, 3, 6, 9\}\). Năng lượng bắt đầu truyền ở trạm \(1\): trạm \(1 \to\) trạm \(3 \to\) trạm \(6 \to\) trạm \(9\). Vậy \(K = 3\) là giá trị nhỏ nhất thỏa mãn.