Doraemon đ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).

Doraemon có khả năng truyền năng lượng trong phạm vi hoạt động ~K~ ~(K \ge 0)~. Doraemon 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, Doraemon 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~).

Nhiệm vụ của bạn là giúp Doraemon tìm ra 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~.

Input

• 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, \dots, 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.

Output

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~.

Scoring

Sample Input 1

9
9 8 8 0 0 8 0 0 9

Sample Output 1

3

Notes

• Với ~K = 3~, chỉ những trạm có khả năng ~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 \rightarrow~ trạm ~3 \rightarrow~ trạm ~6 \rightarrow~ trạm ~9~.

• Cuối cùng, năng lượng đến được trạm ~9 \Rightarrow K = 3~ là giá trị nhỏ nhất thỏa mãn.