// You are given an array of N integers.
//You can either take an element and add it to your sum or skip it. 
//However, if you take an element, you cannot take the next element. 
//Find the maximum sum you can obtain.
 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;cin>>n; int arr[n];
	for(int i=0;i<n;i++)
	cin>>arr[i];
 
	vector<int>dp(n,0);
	dp[0]=arr[0];
	dp[1]=max(arr[0], arr[1]);
	for(int i=2;i<n;i++){
		dp[i]=max(arr[i]+dp[i-2], dp[i-1]);
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

Ly8gWW91IGFyZSBnaXZlbiBhbiBhcnJheSBvZiBOIGludGVnZXJzLgovL1lvdSBjYW4gZWl0aGVyIHRha2UgYW4gZWxlbWVudCBhbmQgYWRkIGl0IHRvIHlvdXIgc3VtIG9yIHNraXAgaXQuIAovL0hvd2V2ZXIsIGlmIHlvdSB0YWtlIGFuIGVsZW1lbnQsIHlvdSBjYW5ub3QgdGFrZSB0aGUgbmV4dCBlbGVtZW50LiAKLy9GaW5kIHRoZSBtYXhpbXVtIHN1bSB5b3UgY2FuIG9idGFpbi4KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CglpbnQgbjtjaW4+Pm47IGludCBhcnJbbl07Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJY2luPj5hcnJbaV07CgkKCXZlY3RvcjxpbnQ+ZHAobiwwKTsKCWRwWzBdPWFyclswXTsKCWRwWzFdPW1heChhcnJbMF0sIGFyclsxXSk7Cglmb3IoaW50IGk9MjtpPG47aSsrKXsKCQlkcFtpXT1tYXgoYXJyW2ldK2RwW2ktMl0sIGRwW2ktMV0pOwoJfQoJY291dDw8ZHBbbi0xXTw8ZW5kbDsKCXJldHVybiAwOwp9

OAoxCi0yCjMKMTIKLTUKMQo2Ci0z

8
1
-2
3
12
-5
1
6
-3