Bài 2: Đề chọn vòng 2 Yên Thành năm 2024-2025

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

Dữ liệu:

Đọc vào từ file BAI2.INP

• 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 ~a_i~ (~1 ≤ ai ≤ 10^9~). Cánh cửa thứ ~i~ sẽ mở ra mỗi ~a_i~ giây.

Kết quả:

Ghi ra file BAI2.OUT 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ụ 1:**
    BAI2.INP
    4 
    3 2 3 4
    BAI2.OUT
    8
**Ví dụ 2:**
    BAI2.INP
    6
    4 5 4 5 4 5
    BAI2.OUT
    15

Giải thích:

Ở ví dụ 1: Long sẽ thoát ra 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