Nguồn đề: Beginner Free Contest 24

Đề bài: https://drive.google.com/file/d/15Twi2BfkzcuK3jgO57Tbiw62-SNG1PnM/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1EYgp2ui1N63-H-n1FGLTtTaRGzqXTetJ/view?usp=sharing

Bài giải: https://drive.google.com/file/d/15rfCyF76k7KJ8zbrbtdwjaLeHXu5HUWV/view?usp=sharing

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 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ánh cửa đều đóng. Sau đó, cánh cửa thứ i sẽ chỉ mở ra mỗi ~a_i~ 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.

Input

Dòng 1: n - số lượng cánh cửa có trong mê cung ~(1 ≤ n ≤ 10^5).~

Dòng 2: n số nguyên ~a_i~ - cánh cửa thứ i sẽ mở ra mỗi ~a_i~ giây ~(1 ≤ a_i ≤ 10^9).~

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.

Sample Input 1

4
3 2 3 4

Sample Output 1

8

Sample Input 2

5
2 2 2 3 3

Sample Output 2

3

Sample Input 3

6
4 5 4 5 4 5

Sample Output 3

15

Sample Input 4

10
2 4 6 8 10 2 4 6 8 10

Sample Output 4

20

Giải thích

Ở ví dụ 1, Long sẽ thoát khỏi mê cung như sau:

• Long ở phòng 1 tại thời điểm 0, cửa 1 đóng, đợi qua 3 giây để cửa 1 mở, Long đi qua phòng 2.
• Long ở phòng 2 tại thời điểm 3, cửa 2 đóng, đợi qua 1 giây để cửa 2 mở, Long đi qua phòng 3.
• Long ở phòng 3 tại thời điểm 4, cửa 3 đóng, đợi qua 2 giây để cửa 3 mở, Long đi qua phòng 4.
• Long ở phòng 4 tại thời điểm 6, cửa 4 đóng, đợi qua 2 giây để cửa 4 mở, Lòng đi qua phòng 5 và thoát khỏi mê cung.

Vì tổng thời gian ít nhất cần để thoát mê cung là 8 giây nên ta in ra 8.