Cho một chiếc cầu thang gồm n bậc, mỗi bậc được gán một chi phí aᵢ.

Người chơi có thể bắt đầu từ bậc số 0 hoặc bậc số 1.

Từ một bậc bất kỳ, bạn có thể:</p>

• Bước 1 bậc (đến bậc i + 1)
• Hoặc bước 2 bậc (đến bậc i + 2)

Mỗi khi bước vào một bậc, bạn phải trả chi phí aᵢ tương ứng. Hãy tính tổng chi phí tối thiểu để lên đến đỉnh cầu thang (ngay sau bậc cuối cùng).

Input:

• Dòng đầu tiên chứa một số nguyên n — số lượng bậc cầu thang.
• Dòng thứ hai chứa n số nguyên a₁, a₂, ..., aₙ — chi phí của từng bậc.

Output:

• Một số nguyên duy nhất — chi phí tối thiểu để lên đỉnh cầu thang.

Ràng buộc:

• 2 ≤ n ≤ 10⁵
• 0 ≤ aᵢ ≤ 1000

Ví dụ:

Ví dụ 1:

Input:
3
10 15 20

Output:
15

Phân tích:

Số bậc: n = 3 → gồm 3 bậc: 0, 1, 2

Chi phí từng bậc:

• Bậc 0: 10
• Bậc 1: 15
• Bậc 2: 20

Mục tiêu là vượt qua bậc 2 để đến đỉnh.

Các cách đi hợp lệ:

1. Bắt đầu từ bậc 0 → bước đến bậc 1 → bước đến bậc 2 → đỉnh
   Chi phí: 10 + 15 + 20 = 45
2. Bắt đầu từ bậc 0 → bước 2 bậc đến bậc 2 → đỉnh
   Chi phí: 10 + 20 = 30
3. Bắt đầu từ bậc 1 → bước 2 bậc lên đỉnh
   Chi phí: 15

Lựa chọn tối ưu là bắt đầu từ bậc 1 và bước thẳng lên đỉnh. Do đó, chi phí tối thiểu là 15.

Ví dụ 2:

Input:
10
1 100 1 1 1 100 1 1 100 1

Output:
6

Giải thích:

• Bậc 0 → trả 1
• Bậc 2 → trả 1
• Bậc 4 → trả 1
• Bậc 6 → trả 1
• Bậc 7 → trả 1
• Bậc 9 → trả 1

Tổng chi phí: 1 + 1 + 1 + 1 + 1 + 1 = 6