#include <iostream>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;
const int VERYLONGINT = 1000000001;

struct tf {
    vector<int> tree;
    int size;
    tf(int n) {
        size = n + 1;
        tree.assign(n + 1, 0);
    }
    void add(int p, int v) {
        for (int i = p + 1; i < size; i += (i & (-i)))
            tree[i] += v;
    }

};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    ll cf = 0;
    vector<pair<ll, ll>> cn;
    int cnt = 1;
    for (int i = 1; i < n; i++)
        if (a[i - 1] != a[i]) {
            cn.push_back({ a[i - 1], cnt });
            cnt = 1;
        }
        else
            cnt++;
    cn.push_back({ a[n - 1], cnt });
    int j = cn.size() - 1;
    int i = 0;
    ll res = 0;
    while (i != j) {
        cn[i].first = max(0ll, cn[i].first - cf);
        ll pc = cf;
        cf += cn[i].first;
        while (i != j - 1 && cn[i].first >= cn[j].second) {
            res += (cn[j].first - pc) * cn[j].second;
            cn[i].first -= cn[j].second;
            j--;
            pc += cn[j].second;
        }
        res += (cn[j].first - pc) * cn[i].first;
        i++;
    }
    cn[i].first = max(0ll, cn[i].first - cf);
    res += cn[i].second * cn[i].first;
    cout << res << "\n";
    return 0;
}