1292: ALGO의 고민
Memory Limit：1024 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：3
Solved：3
Description
ALGO는 알고리즘 공부에 푹 빠진 학생입니다.
ALGO는 N일 동안 매일매일 특별한 과제를 수행해야 합니다.
각 과제는 당일에만 수행할 수 있으며, 과제를 수행하면 특정 점수를 얻습니다.
하지만 ALGO는 체력이 약해서, 과제를 수행한 다음 날은 반드시 쉬어야 합니다.
즉, 과제를 수행하면 그 다음 날은 과제를 수행할 수 없습니다.
또한, ALGO는 연속으로 쉴 수는 없습니다.
즉, 하루 쉬었다면 그 다음 날은 반드시 과제를 수행해야 합니다 (단, 마지막 날이 휴식일이 되는 것은 가능합니다).
ALGO는 N일 동안 얻을 수 있는 총 점수의 최댓값을 구하고 싶습니다.
Input
첫째 줄에 정수 N (1 ≤ N ≤ 100,000)이 주어집니다. 둘째 줄에 N개의 정수 S1,S2,…,SN ()이 주어집니다. Si는 i번째 날 과제를 수행했을 때 얻을 수 있는 점수입니다.
Output
첫째 줄에 ALGO가 얻을 수 있는 총 점수의 최댓값을 출력합니다.
Sample Input Copy
5
10 20 30 40 50Sample Output Copy
90