#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int lint
#define all(x) x.begin(), x.end()
#define die(x) { cout << (x); return 0; }

using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
const int inf = 1000*1000*1000 + 7;
typedef list<int>::iterator lit;

map< int, vector<lit> > m;
list<int> arr;

signed main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    int n, prv, cur;
    cin >> n >> prv;
    arr.push_back(prv);
    m[prv].push_back(--arr.end());
    int ma = prv;

    for (int i = 1; i < n; i++) {
        cin >> cur;
        ma = max(ma, cur);
        if (cur == prv) continue;
        arr.push_back(cur);
        m[cur].push_back(--arr.end());
        prv = cur;
    }

    int ans = 0;
    while (m.size() > 1) {
        vector<lit>& v = m.rbegin()->second;
//        for (int i = 0; i < v.size(); i++)
//            cout << *v[i] << ' ';
//        cout << '\n';
        for (int i = 0; i < v.size(); i++) {
            lit it = v[i];
            if (it == arr.begin())
                ans += *it - *(++arr.begin());
            else if (it == --arr.end())
                ans += *it - *(-- --arr.end());
            else {
                lit r = --it; ++it;
                lit l = ++it; --it;
                ans += *it - max(*l, *r);
            }
        }
        for (int i = 0; i < v.size(); i++) {
//            if (v[i] != arr.begin() && v[i] != -- arr.end()) {
//                lit r = --v[i]; ++v[i];
//                lit l = ++v[i]; --v[i];
//                if (*l == *r)
//                    arr.erase(r);
//            }
            arr.erase(v[i]);
        }
        m.erase(m.rbegin()->first);
    }

    cout << max(ma, ans + *arr.begin());

    return 0;
}
