"""
(실전 문제) 개미 전사

- [ 개미 전사 ]는 부족한 식량을 충당하고자 메뚜기 마을의 [ 식량창고를 몰래 "공격" ]하려고 한다.

- [ 메뚜기 마을 ]에는 식량창고가 [ 일직선으로 이어져 ] 있다.

- 일직선상에 존재하는 식량창고 중에 [ 서로 인접한 식량창고가 공격받으면 ] 바로 알아챌 수 있다.

★ 따라서, 개미 전사는 [ 최소한 한 칸 이상 떨어진 ] 식량창고를 약탈해야 한다.
  
예를 들어 식량창고가 아래와 같이 4개가 존재한다고 가정.
{1, 3, 1, 5}

- 이때 개미전사는 두 번째 , 네 번째 식량창고를 선택했을 때 
  최댓값인 총 8개의 식량을 빼앗을 수 있다.
- 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때
  [ 식량의 최댓값 ] 을 구하는 프로그램을 작성하시오.
------------------------------------------------------------------------------
[ 입력 조건 ]

- [ 첫째 줄 ]에 식량창고 N이 주어진다. (3 <= N <= 100)  
- [ 둘째 줄 ]에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다.( 0<= K <=1,000)

[ 출력 조건 ]
- 첫째 줄에 [ 개미 전사가 얻을 수 있는 ] [ ** 식량의 최댓값을 출력 ** ]한다.

[ 입력 ]                     [ 출력 ]
  4
1  3  1  5                      8
   
※ dp 테이블을 특정 크기만큼 만들어주고, 점화식에 맞게 하나씩 채워주면 된다.
   즉, 점화식을 찾는게 dp에서 가장큰 핵심이라고 할 수 있다.
# 바로 앞에있는것이랑, 두번째 앞에 있는것을 비교해 주면 된다.
"""


# 책 정답 8-6.py (p, 222) 

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
# n의 조건이 100개까지 주어질수 있다고 해서
# 미리 100까지 주어진 것이다. --> 조건만큼 할당해주는게 일반적이다.
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]  # [ 첫 번째 ] 식량저장창고 까지의 얻을수 있는 최댓값.
d[1] = max(array[0], array[1]) # [ 두 번째 ] 식량저장창고 까지의 얻을수 있는 최댓값.

for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])
    print(d[i])
    
# 계산된 결과 출력
print(d[n - 1])

