#include using namespace std; using ll = long long; const ll inf = 1e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N); for (int i = 0; i < N; i++) cin >> A[i]; ll ans = 0; set> intv; auto add = [&] (ll x) -> void { auto it = intv.lower_bound({x, inf}); if (intv.empty() || it == intv.begin()) { it = intv.insert({x, x + 1}).first; } else { --it; if (it->second == x) { pair v = *it; v.second++; intv.erase(it); it = intv.insert(v).first; } else { it = intv.insert({x, x + 1}).first; } } if (next(it) != intv.end() && it->second == next(it)->first) { pair v = *it; v.second = next(it)->second; intv.erase(next(it)); intv.erase(it); intv.insert(v); } }; auto del = [&] (ll x) -> void { auto it = intv.lower_bound({x, inf}); --it; if (x == it->first) { pair v = *it; v.first++; intv.erase(it); if (v.first != v.second) { intv.insert(v); } } else if (x == it->second - 1) { pair v = *it; v.second--; intv.erase(it); intv.insert(v); } else { pair v = *it; intv.erase(it); intv.insert({v.first, x}); intv.insert({x + 1, v.second}); } }; for (ll a: A) { auto it = intv.lower_bound({a + 1, -inf}); if (it == intv.begin()) { add(a); } else { it--; if (a < (*it).second) { ll L = (*it).first, R = (*it).second - 1; ans += (a - L + 1) * (R - a + 1); del(L + R - a); add(L - 1); add(R + 1); } else { add(a); } } } cout << ans << '\n'; }