stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<queue>

using namespace std;

#pragma warning(disable:4996)

int n, m, q, dist[110000], mark[110000], u[210000], v[210000];

vector<pair<int, int>>x[110000], y[110000], z[110000]; bool used[210000];

bool isgood(int f) {

	for (int i = 0; i < z[f].size(); i++) {

		if (mark[z[f][i].first] == 0 && used[z[f][i].second] == false)return true;

	}

	return false;

}

int main() {

	scanf("%d%d%d", &n, &m, &q); queue<int>Q;

	for (int i = 0; i < m; i++) {

		int a, b; scanf("%d%d", &a, &b); u[i + 1] = a; v[i + 1] = b;

		x[a].push_back(make_pair(b, i + 1)); x[b].push_back(make_pair(a, i + 1));

	}

	Q.push(1); for (int i = 1; i <= n; i++)dist[i] = 999999; dist[1] = 0;

	while (!Q.empty()) {

		int a1 = Q.front(); Q.pop();

		for (int i = 0; i < x[a1].size(); i++) {

			if (dist[x[a1][i].first] > dist[a1] + 1) { dist[x[a1][i].first] = dist[a1] + 1; Q.push(x[a1][i].first); }

		}

	}

	for (int i = 1; i <= n; i++) {

		for (int j = 0; j < x[i].size(); j++) {

			if (dist[i] < dist[x[i][j].first]) { y[i].push_back(x[i][j]); }

			if (dist[i] > dist[x[i][j].first]) { z[i].push_back(x[i][j]); }

		}

	}

	int cnt = 0;

	for (int i = 0; i < q; i++) {

		int a; scanf("%d", &a); used[a] = true;

		int E1 = u[a], E2 = v[a];

		if (dist[E1] == dist[E2]) { cnt += 0; }

		else {

			int a1 = 0; if (dist[E1] < dist[E2])a1 = E2; else a1 = E1;

			if (isgood(a1) == false && mark[a1] == 0) {

				queue<int>Q; Q.push(a1); cnt++; mark[a1] = 1;

				while (!Q.empty()) {

					int a2 = Q.front(); Q.pop();

					for (int j = 0; j < y[a2].size(); j++) {

						if (mark[y[a2][j].first] == 0 && isgood(y[a2][j].first) == false) {

							mark[y[a2][j].first] = 1; Q.push(y[a2][j].first); cnt++;

						}

					}

				}

			}

		}

		printf("%d\n", cnt);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4544768390356448x):
#include<bits/stdc++.h>

using namespace std;

int n,m,q,a[1<<18],b[1<<18],c,dist[1<<18],T[1<<18],cnt,U[1<<18];

vector<pair<int, int> >x[110000],y[110000];bool used[210000];

int main(){

	scanf("%d%d%d",&n,&m,&q);

	for(int i=0;i<m;i++){scanf("%d%d",&a[i],&b[i]);x[a[i]].push_back(make_pair(b[i],i));x[b[i]].push_back(make_pair(a[i],i));}

	fill(dist,dist+n+1,-1);dist[1]=0;queue<int>Q;Q.push(1);

	while(!Q.empty()){int a1=Q.front();Q.pop();for(pair<int,int>i:x[a1]){if(dist[i.first]==-1){dist[i.first]=dist[a1]+1;Q.push(i.first);}}}

	for(int i=1;i<=n;i++){for(pair<int,int>j:x[i]){if(dist[i]<dist[j.first]){y[i].push_back(j);T[j.first]++;}}}

	for(int i=0;i<q;i++){

		scanf("%d",&c);c--;queue<pair<int,int> >Q1; int ss=-1;

		if(dist[a[c]]<dist[b[c]])ss=b[c];

		if(dist[a[c]]>dist[b[c]])ss=a[c];

		if(ss>=1&&U[ss]==0&&used[c]==false){

			Q1.push(make_pair(ss,c));

			while(!Q1.empty()){

				int a1=Q1.front().first,a2=Q1.front().second;Q1.pop();

				if(U[a1]==1||used[a2]==true)continue;T[a1]--;used[a2]=true;if(T[a1]!=0)continue;cnt++;U[a1]=1;

				for(pair<int,int>j:y[a1]){if(U[j.first]==0)Q1.push(j);}

			}

		}

		printf("%d\n",cnt);

	}

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<map> 

#include<list>

#include<string>

#include<cstring>

#include<set>

#include<vector>

#define ll long long

#define memset(a,n) memset(a,n,sizeof(a))

#define mp make_pair 

#define pb push_back

using namespace std;

const int maxn = 2e5 + 100;





int main()

{

	int n;int a[maxn];ll p[maxn];scanf("%d",&n);

	for(int i = 1 ;i <= n;i++) scanf("%d",&a[i]);

	p[1] = a[1];

	for(int i = 3;i <= n;i += 2){

		p[i] = p[i-2] + a[i];

	}

	ll dp[maxn] = {0};

	for(int i = 2; i <= n;i++){

		if(i & 1){

			dp[i] = max(dp[i-1],dp[i-2]+a[i]);

		}else{

			dp[i] = max(dp[i-2] + a[i],p[i-1]);

		}

	}

	printf("%lld\n",dp[n]);

}

// Faster C++ solution for the same problem (measured speedup: 2.6689092456707417x):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;



#define ZERO_IQ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define debug(x, y) cerr<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl

#define debug2(x, y, z) cerr<<(#x)<<" " <<(#y)<<" " <<(#z)<<" is " << (x) <<" "<< (y) <<" "<<(z) << endl

#define watch(x) cerr<<(#x)<<" is " << (x) << endl



const int N = 2e5 + 10;

typedef long long ll;



ll dp[N];



int main() {

    ll n;

    cin >> n;

    vector<ll> v;

    vector<ll> summ(n + 1);

    for (int i = 1; i <= n; i++) {

        ll q;

        cin >> q;

        v.push_back(q);

        if (i % 2 == 1) {

            if (i == 1)summ[i] = q;

            else

                summ[i] = summ[i - 2] + q;

        }

    }

    dp[1] = 0;

    for (int i = 2; i <= n; i++) {

        if (i % 2 == 1) {

            dp[i] = max(dp[i - 2] + v[i - 1], dp[i - 1]);

        } else

            dp[i] = max(dp[i - 2] + v[i - 1], summ[i-1]);

    }

    cout << dp[n];

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<map> 

#include<list>

#include<string>

#include<cstring>

#include<set>

#include<vector>

#define ll long long

#define memset(a,n) memset(a,n,sizeof(a))

#define mp make_pair 

#define pb push_back

using namespace std;

const int maxn = 2e5 + 100;





int main()

{

	int n;int a[maxn];ll p[maxn];scanf("%d",&n);

	for(int i = 1 ;i <= n;i++) scanf("%d",&a[i]);

	p[1] = a[1];

	for(int i = 3;i <= n;i += 2){

		p[i] = p[i-2] + a[i];

	}

	ll dp[maxn] = {0};

	for(int i = 2; i <= n;i++){

		if(i & 1){

			dp[i] = max(dp[i-1],dp[i-2]+a[i]);

		}else{

			dp[i] = max(dp[i-2] + a[i],p[i-1]);

		}

	}

	printf("%lld\n",dp[n]);

}

// Faster C++ solution for the same problem (measured speedup: 2.72557645745638x):
#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<vector>

#include<functional>

using namespace std;

typedef long long LL;

inline LL read()

{

	LL kk=0,f=1;

	char cc=getchar();

	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}

	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}

	return kk*f;

}

LL a[2000222],dp[4],n,sum[2000222];

#define P(x) (x%3+3)%3

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

	{

		a[i]=read();

		sum[i]=sum[i-1];

		if(i&1)sum[i]+=a[i];

	}

	dp[1]=0;dp[2]=max(a[1],a[2]);

	for(int i=3;i<=n;++i)

	{

		LL now,pre1,pre2;

		now=P(i);pre1=P(i-1);pre2=P(i-2);

		dp[now]=0;

		if(i&1)

		{

			dp[now]=max(dp[pre1],dp[pre2]+a[i]);

		}

		else

		{

			dp[now]=max(sum[i],dp[pre2]+a[i]);

		}

	}

	printf("%lld\n",dp[P(n)]);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

#include<queue>

#include<stack>

using namespace std;

typedef unsigned long long ull;

typedef  long long ll;

#define INF  0x7f7f7f7f//7f7f7f7f

#define M 2000010

#define N 100010

const ll mod = 1e9 + 7;

ll a[M],dp[M],sum[M],n;

int main(void){

	scanf("%lld",&n);

	for(ll i = 1;i <= n;i++){

		scanf("%lld",&a[i]);

		if(i%2)

		sum[i] =sum[i-1]+a[i];

		else

		sum[i] =sum[i-1];

	}

	for(ll i = 2;i <= n;i++){

		if(i%2)

		dp[i] =max(dp[i-2]+a[i],dp[i-1]);

		else

		dp[i] =max(dp[i-2]+a[i],sum[i-1]);

	}

	printf("%lld\n",dp[n]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.177672154364713x):
#include <stdio.h>

#define N 200002

typedef long long LL;



int a[N];

LL s[N][2];



int read()

{

	char c, f = 0;

	while((c = getchar()) < 48 || c > 57){

		if(c == '-') f = 1;

	}

	int x;

	if(!f){

		x = c - 48;

		while((c = getchar()) > 47 && c < 58) x = x * 10 + (c - 48);

	}

	else{

		x = 48 - c;

		while((c = getchar()) > 47 && c < 58) x = x * 10 - (c - 48);

	}

	return x;

}



int main()

{		

	int n, i;

	LL s1 = 0, s2 = 0, t, x;

	

	scanf("%d", &n);

	for(i = 1; i <= n; i++){

		a[i] = read();

	}

	if(n % 2 == 0){

		s[1][0] = (LL)a[1], s[2][0] = (LL)a[2];

		for(i = 3; i <= n; i++){

			if(i & 1){

				s[i][0] = s[i - 2][0] + (LL)a[i];

			}

			else{

				t = s[i - 2][0];

				if((x = s[i - 3][0]) > t) t = x;

				s[i][0] = t + (LL)a[i];

			}

		}

		t = s[n][0];

		if((x = s[n - 1][0]) > t) t = x;

		printf("%lld\n", t);

		return 0;

	}

	

	s[1][0] = (LL)a[1], s[2][0] = (LL)a[2];

	s[3][1] = (LL)a[3], s[3][0] = (LL)(a[1] + a[3]);

	for(i = 4; i <= n; i++){

		if(i & 1){

			s[i][0] = s[i - 2][0] + (LL)a[i];

			t = s[i - 2][1];

			if((x = s[i - 3][0]) > t) t = x;

			if((x = s[i - 4][0]) > t) t = x;

			s[i][1] = t + (LL)a[i];

		}

		else{

			t = s[i - 2][0];

			if((x = s[i - 3][0]) > t) t = x;

			s[i][0] = t + (LL)a[i];

		}

	}

	t = s[n][1];

	if((x = s[n - 1][0]) > t) t = x;

	if((x = s[n - 2][0]) > t) t = x;

	printf("%lld\n", t);

			

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define inf 100000000000000000ll

using namespace std;

int n;

ll mem[200005][3], ara[200005];

bool vis[200005][3];

ll dp(int pos, int skip)

{

    if(pos>=n || (pos==n-1 && skip==2))return 0;

    if(vis[pos][skip])return mem[pos][skip];

    vis[pos][skip]= 1;

    mem[pos][skip]= -inf;

    if(skip)mem[pos][skip]= dp(pos+1, skip-1);

    mem[pos][skip]= max(mem[pos][skip], ara[pos]+dp(pos+2, skip));

    return mem[pos][skip];

}

int main()

{

    scanf("%d", &n);

    for(int i=0; i<n; i++)scanf("%lld", &ara[i]);

    ll res= -inf;

    if(!(n&1))

    {

        memset(vis, 0, sizeof vis);

        res= max(res, ara[0]+dp(2, 1));

        memset(vis, 0, sizeof vis);

        res= max(res, ara[1]+dp(3, 0));

    }

    else

    {

        memset(vis, 0, sizeof vis);

        res= max(res, ara[0]+dp(2, 2));

        memset(vis, 0, sizeof vis);

        res= max(res, ara[1]+dp(3, 1));

        memset(vis, 0, sizeof vis);

        res= max(res, ara[2]+dp(4, 0));

    }

    printf("%lld\n", res);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7146923981818833x):
#include<bits/stdc++.h>

#define ll long long

#define inf 100000000000000000ll

using namespace std;

int n;

ll mem[200005][3], ara[200005];

bool vis[200005][3];

ll dp(int pos, int skip)

{

    if(pos>=n || (pos==n-1 && skip==2))return 0;

    if(vis[pos][skip])return mem[pos][skip];

    vis[pos][skip]= 1;

    mem[pos][skip]= -inf;

    if(skip)mem[pos][skip]= dp(pos+1, skip-1);

    mem[pos][skip]= max(mem[pos][skip], ara[pos]+dp(pos+2, skip));

    return mem[pos][skip];

}

int main()

{

    scanf("%d", &n);

    for(int i=0; i<n; i++)scanf("%lld", &ara[i]);

    ll res= -inf;

    if(!(n&1))

    {

        //memset(vis, 0, sizeof vis);

        res= max(res, ara[0]+dp(2, 1));

        //memset(vis, 0, sizeof vis);

        res= max(res, ara[1]+dp(3, 0));

    }

    else

    {

        //memset(vis, 0, sizeof vis);

        res= max(res, ara[0]+dp(2, 2));

        //memset(vis, 0, sizeof vis);

        res= max(res, ara[1]+dp(3, 1));

        //memset(vis, 0, sizeof vis);

        res= max(res, ara[2]+dp(4, 0));

    }

    printf("%lld\n", res);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

#define all(v) v.begin(), v.end()

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 12.193690643594786x):
#include<iostream>

#include<cstdio>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include <map>

#include <math.h>

#include <vector>

#include <queue>

#include <stack>

#include <list>

#include <limits.h>

#include <string>

#include<functional>

#include <set>

#include <utility>

#include <iomanip>

#include <string>

#define INF 1<<30

#define MO 1000000007

#define MI 998244353

#define ll long long

#define woo 140737488355327

using namespace std;

int a[2100010];ll dp[2100001][3];

int main()

{

    int n;scanf("%d",&n);

    for(int i=0;i<n;i++)

      scanf("%d",&a[i]);

    ll ans;

    if(n%2==0)

    {

    dp[0][0]=a[0];dp[0][1]=a[1];

    for(int i=2;i<n;i+=2)

    {

        dp[i/2][0]=dp[i/2-1][0]+a[i];

        dp[i/2][1]=max(dp[i/2-1][0]+a[i+1],dp[i/2-1][1]+a[i+1]);

    }

    ans=max(dp[n/2-1][0],dp[n/2-1][1]);

    }

    else

    {

    dp[0][0]=a[0];dp[0][1]=a[1];dp[0][2]=a[2];

    for(int i=1;i<n/2;i++)

    {

        dp[i][0]=dp[i-1][0]+a[i*2];

        dp[i][1]=max(dp[i-1][0]+a[i*2+1],dp[i-1][1]+a[i*2+1]);

        dp[i][2]=max(max(dp[i-1][0]+a[i*2+2],dp[i-1][1]+a[i*2+2]),dp[i-1][2]+a[i*2+2]);

    }

    ans=max(dp[n/2-1][0],max(dp[n/2-1][1],dp[n/2-1][2]));

    }

    printf("%lld\n",ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

#define all(v) v.begin(), v.end()

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 12.194405218254417x):
//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

#include<queue>

#include<stack>

using namespace std;

typedef unsigned long long ull;

typedef  long long ll;

#define INF  0x7f7f7f7f//7f7f7f7f

#define M 2000010

#define N 100010

const ll mod = 1e9 + 7;

ll a[M],dp[M],sum[M],n;

int main(void){

	scanf("%lld",&n);

	for(ll i = 1;i <= n;i++){

		scanf("%lld",&a[i]);

		if(i%2)

		sum[i] =sum[i-1]+a[i];

		else

		sum[i] =sum[i-1];

	}

	for(ll i = 2;i <= n;i++){

		if(i%2)

		dp[i] =max(dp[i-2]+a[i],dp[i-1]);

		else

		dp[i] =max(dp[i-2]+a[i],sum[i-1]);

	}

	printf("%lld\n",dp[n]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

#define all(v) v.begin(), v.end()

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 11.986458541133786x):
#include <bits/stdc++.h>

using namespace std;



long long dp[200005],sum[200005],s[200005];



int main()

{

    int n;

    while(cin>>n)

    {

        for(int i=1;i<=n;i++)

            cin>>s[i];

        for(int i=1;i<=n;i++)

        {

            if(i==1)

                sum[i]=s[i];

            else

                sum[i]=sum[i-2]+s[i];

        }

        for(int i=2;i<=n;i++)

        {

            if(i%2==0)

            {

                dp[i]=max(dp[i-2]+s[i],sum[i-1]);

            }

            else

            {

                dp[i]=max(dp[i-2]+s[i],dp[i-1]);

            }

        }

        cout<<dp[n]<<endl;

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

#define all(v) v.begin(), v.end()

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 11.611004997036579x):
#include <bits/stdc++.h>



#define forn(i, n) for (int i = 0; i < int(n); ++i)

#define for1(i, n) for (int i = 1; i <= int(n); ++i)

#define ms(a, x) memset(a, x, sizeof(a))

#define F first

#define S second

#define all(x) (x).begin(),(x).end()



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

mt19937 gen(random_device{}());

template<typename... Args> void write(Args... args) { ((cout << args << " "), ...); cout<<endl;}



int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin>>n;

    vector<int> a(n+1);

    for(int i=1;i<=n;++i) cin>>a[i];

    vector<vector<ll>> dp(n+1,vector<ll>(3,-1e18));

    dp[1]={0,0,0};

    for(int i=2;i<=n;++i){

        if(i&1){

            dp[i][0]=max({dp[i-2][0],dp[i-2][1],dp[i-2][2]})+a[i];

            dp[i][1]=dp[i-1][0];

            dp[i][2]=dp[i-1][1];

        }else{

            dp[i][0]=max({dp[i-1][1]+a[i],dp[i-1][2]+a[i]});

            dp[i][1]=dp[i-1][2]+a[i-1];

        }

    }

    cout<<*max_element(all(dp[n]));

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

#define all(v) v.begin(), v.end()

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.0293582044451535x):
#pragma GCC optimize("O3")



#include <bits/stdc++.h>



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

#define F first

#define S second

#define pii pair<int,int>

#define pll pair<ll, ll>

#define vi vector<int>

#define vll vector<ll>

#define vii vector<pii>

#define read(FILE)  freopen(FILE, "r", stdin);

#define out(FILE) freopen(FILE, "w", stdout);

#define clr(x, y) memset(x,y,sizeof(x));

#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

#define all(x) x.begin(),x.end()

#define rep(i, m, n) for(int i=m ; i<n ; i++)

#define forr(i, m, n) for(ll i=m ; i<=n ; i++)

#define endl '\n'

#define pb push_back

#define re return

const int N = 2e5 + 5;

const ll OO = 1e15;

using namespace std;

ll n;

ll arr[N];

ll dp[N][3];



ll solve(ll i, ll c) {

    if (i > n) {

        re c ? -OO : 0;

    }

    ll &ret = dp[i][c];

    if (~ret) re ret;

    ret = -OO;

    if (c) {

        ret = max(ret, solve(i + 1, c - 1));

    }

    ret = max(ret, arr[i] + solve(i + 2, c));

    re ret;

}



int main() {

    cin >> n;

    rep(i, 0, n) {

        cin >> arr[i];

    }

    /*rep(i, 0, N) {

        rep(j, 0, 3) {

            dp[i][j] = OO;

        }

    }*/

    clr(dp, -1);

    cout << solve(0, (n & 1) + 1);



}