#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int N = 1000005;
int n;
int pre[N], suf[N];
ll w[N];
bool vis[N];
bool instk[N];
queue <int> pos;

void ck(int x) {
    if (x < 1 || x > n) return ;
    if (pre[x] == 0) return ;
    if (suf[x] == n + 1) return ;
    if (w[pre[x]] <= w[x] && w[suf[x]] <= w[x] && !instk[x]) pos.push(x), instk[x] = 1;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++) cin >> w[i], sum += w[i];
    for (int i = 1; i <= n; i++) pre[i] = i - 1, suf[i] = i + 1;
    for (int i = 2; i < n; i++) ck(i);
//    cout << pos.size() << endl;
    while (!pos.empty()) {
        int x = pos.front();
        pos.pop();
        //cout << x << endl;
        instk[x] = 0;
        if (vis[x]) continue;
        if (pre[x] == 0 || suf[x] == n + 1) continue;
        if (w[pre[x]] > w[x] || w[suf[x]] > w[x]) continue;
        w[x] = w[pre[x]] + w[suf[x]] - w[x];
        int l = pre[pre[x]], r = suf[suf[x]];
        vis[pre[x]] = 1;
        vis[suf[x]] = 1;
        suf[l] = x;
        pre[r] = x;
        pre[x] = l;
        suf[x] = r;
        ck(l);
        ck(r);
        ck(x);
    }
    vector <ll> val;
    for (int i = 1; i <= n; i++) if (!vis[i]) val.push_back(w[i]);
//    cout << endl;
    sort(val.begin(), val.end());
    reverse(val.begin(), val.end());
    ll ans = 0;
    for (int i = 0; i < (int)val.size(); i++) {
        if (i % 2 == 0) ans += val[i];
        else ans -= val[i];
    }
    assert((sum + ans) % 2 == 0);
    cout << (sum + ans) / 2;
    QwQ330AwA;
}