#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
int n, a[1000006],  r, p, ans, sum, l;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p;
		sum += p;
		a[++r] = p;
		while (r >= 3 && a[r - 2] < a[r - 1] && a[r - 1] >= a[r]) {
			a[r - 2] = (a[r - 2] + a[r] - a[r - 1]);
			r -= 2;
		}
	}
	l = 1;
	int op = 1;
	while (l <= r) {
		if (a[l] > a[r]) {
			ans += op * a[l];
			l++;
		} else {
			ans += op * a[r];
			r--;
		}
		op = -op;
	}
	cout << (sum + ans) / 2;
}
//sub1,2 dp，白送
//sub3 直接取左右两边较大的
//感觉很对，证明不清楚

//然后正解

//可以说明在左右两侧都是间隔取
//因为非间隔一定会有一个人利益受损，那么这个人就不会让对方非间隔取（在对方后面直接跟）

//如果自己不优自己更不会非间隔取
//所以一定是交错的取的

//然后就两种思路
//第一种是把v形段缩到一起
//第二种是把原序列缩成v形段

//显然，第一种思路太naive了，我们考虑第二种
//怎么才能让原序列变成一个v形段呢

//如果有 ^ 存在，考虑等效权值，肯定是两边的数减去中间的

//所以不会再有^状的出现，就再按照sub3做就好了

//然后等号是可以取的吧，应该