Single-width adjacent caves in a row each hold some gold coins. A fixed-width stone door, initially blocking three unspecified caves, can be shifted exactly once to cover any set of three consecutive caves. No cave can be accessed before shifting; after shifting, only unblocked caves are collectible. Given the number of caves and their individual gold counts, calculate the maximum total gold obtainible.

For example, with 5 caves holding [7, 2, 12, 5, 3]:

• Block left 3 → collect 5+3=8
• Block middle 3 → collect 7+3=10
• Block right 3 → collect7+2=9 The optimal result is 10.

Input Format

1. First line: A positive integer n (4 ≤ n ≤ 20), the total number of caves.
2. Second line: A space-separated string of n positive integers (each 1–20), representing gold in left-to-right order.

Output Format

A single integer: the maximum collectible gold.

Sample Input 1

5
7 2 12 5 3

Sample Output 1

10

Sample Input 2

7
4 18 2 10 7 16 1

Sample Output 2

39

---

Solution Code 1 (Total Minus Sliding Trio Sums)

cave_count = int(input())
gold_values = list(map(int, input().split()))
total_gold = sum(gold_values)
best_total = 0

for left_pos in range(cave_count - 2):
    blocked_sum = 0
    for offset in range(3):
        blocked_sum += gold_values[left_pos + offset]
    current_collect = total_gold - blocked_sum
    if current_collect > best_total:
        best_total = current_collect

print(best_total)

Solution Code 2 (Sliding Window Min Blocked Sum)

cave_count = int(input())
gold_values = list(map(int, input().split()))
total_gold = sum(gold_values)

# Initialize first window sum
min_block = sum(gold_values[0:3])
current_block = min_block

# Slide window from second position
for i in range(1, cave_count - 2 + 1):
    current_block = current_block - gold_values[i-1] + gold_values[i+2]
    if current_block < min_block:
        min_block = current_block

print(total_gold - min_block)