Small là một người đam mê khoa học, đặc biệt vật lý và các hiện tượng tự nhiên. Hôm nay, anh ấy thực hiện thí nghiệm nhằm đo tốc độ cháy của rơm khi được xếp thành những cấu hình khác nhau.

Small xếp các bó rơm thành \(n\) chồng liên tiếp nhau trên một mặt bằng, đánh số từ trái sang phải là \(1, 2, \dots, n\). Chồng rơm thứ \(i\) gồm có \(h_i\) bó rơm xếp chồng lên nhau.

Để bắt đầu thí nghiệm, Small châm lửa cùng lúc vào tất cả các bó rơm nằm ở lớp ngoài cùng. Cụ thể là những bó rơm mà bên trái, bên phải, hoặc bên trên nó không có rơm (tức là những phần tiếp xúc trực tiếp với không khí).

Toàn bộ chồng rơm sẽ cháy dần như sau:

• Mỗi bó rơm mất đúng \(1\) phút để cháy hết hoàn toàn.
• Ngay khi một bó rơm cháy xong hết, lửa sẽ lan sang tất cả các bó rơm nằm kề sát nó (ngay bên trái, bên phải, bên trên, và bên dưới). Lập tức, các bó rơm bên cạnh này sẽ bắt lửa và bắt đầu cháy.

Yêu cầu: Hãy giúp Small tính thời điểm mà toàn bộ \(n\) chồng rơm này cháy hết.

Input

Vào từ file văn bản FIRE.INP:

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\) (\(0 \le h_i \le 10^9\)).

Output

Ghi ra file văn bản FIRE.OUT:

• Một số nguyên là thời điểm cháy hết của \(n\) chồng rơm (tính theo phút).

Example

5
2 3 4 2 3

3

1
0

0

Scoring

• Subtask 1 (\(50\%\) số điểm): \(n, h_i \le 200\).
• Subtask 2 (\(20\%\) số điểm): \(n \le 2000\).
• Subtask 3 (\(30\%\) số điểm): không có ràng buộc gì thêm.