Long đang trên đường đi học thì không may bị một kẻ xấu bắt nhốt vào trong một mê cung. Mê cung gồm n + 1 căn phòng xếp nối tiếp nhau theo thứ tự phòng 1, phòng 2, ..., phòng n + 1. Long hiện đang ở phòng 1, và lối thoát ở phòng n + 1. Giữa n + 1 căn phòng có n cánh cửa. Ban đầu tại thời điểm 0, tất cả các cánh cửa đều đóng. Sau đó, cánh cửa thứ i sẽ chỉ mở ra mỗi ai giây. Do Long khá nhanh nhẹn nên cậu có thể di chuyển giữa 2 căn phòng mà không mất thời gian nào. Long bắt đầu di chuyển tại phòng 1 từ thời điểm 0. Câu hỏi đặt ra cho bạn đó là hãy tìm thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung.

Dữ liệu:

• Dòng đầu tiên gồm một số nguyên n (1 ≤ n ≤ 10^5 ). Số lượng phòng có trong mê cung.
• Dòng thứ hai gồm n số nguyên ai (1 ≤ ai ≤ 10^9 ). Cánh cửa thứ i sẽ mở ra mỗi ai giây.

Kết quả:

• In ra một số nguyên duy nhất là thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung

Ví dụ:

Input

4 
3 2 3 4

Output

8

Ví dụ 2:

Input

5 
2 2 2 3 3

Output

3

Ví dụ 3:

Input

6
4 5 4 5 4 5

Output

15

Nguồn