Doraemon đang du hành trong vũ trụ thì phát hiện có n trạm không gian được xếp trên một tuyến thẳng. 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\).

Doraemon muốn truyền năng lượng với một mức năng lượng cố định K.

Một trạm chỉ có thể tham gia quá trình truyền năng lượng nếu:

Ban đầu, Doraemon nạp năng lượng cho trạm 1.

Sau khi một trạm nhận được năng lượng, trạm đó có thể truyền tiếp năng lượng sang bên phải cho một trạm khác có chỉ số cách nó không quá K. Nói cách khác, nếu trạm hiện tại là i, nó có thể truyền đến các trạm có chỉ số trong đoạn:

miễn là trạm nhận cũng có khả năng tiếp nhận năng lượng ít nhất K.

Yêu cầu

Hãy tìm 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.

Dữ liệu đảm bảo luôn tồn tại ít nhất một giá trị K thỏa 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 chứa n số nguyên \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le n\)).

Output

• In ra một số nguyên dương duy nhất là giá trị nhỏ nhất của K.

Example

9
9 8 8 0 0 8 0 0 9

3

1, 2, 3, 6, 9

1 -> 3 -> 6 -> 9