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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<int> A(N+1), pos(N+1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        pos[A[i]] = i; // l?u v? trí 1-based
    }

    ll ans = 0;
    // t?ng s? ?o?n = N*(N+1)/2 (dùng n?u c?n cho mex=0 nh?ng contribution c?a 0 là 0)
    // X? lý x = 0 riêng (nh?ng vì 0 * count0 = 0 nên không ?nh h??ng ans).
    // Kh?i t?o L,R v?i v? trí c?a 0 (sau ?ó vòng for x t? 1..N-1 dùng L,R là range c?a 0..x-1)
    int L = pos[0], R = pos[0];

    for (int x = 1; x <= N-1; ++x) {
        // hi?n t?i L,R là min/max c?a pos[0..x-1]
        int px = pos[x];
        ll total_with_LR = (ll)L * (ll)(N - R + 1);
        ll include_px = (ll)min(L, px) * (ll)(N - max(R, px) + 1);
        ll count_x = total_with_LR - include_px;
        ans += (ll)x * count_x;
        // m? r?ng L,R ?? ch?a pos[x] cho l?n x+1
        L = min(L, px);
        R = max(R, px);
    }

    // tr??ng h?p mex = N: ?o?n ph?i ch?a t?t c? 0..N-1, t?c ch?a [L,R] v?i L,R hi?n t?i (sau vòng)
    // s? ?o?n ch?a [L,R] là L * (N - R + 1)
    ll cntN = (ll)L * (ll)(N - R + 1);
    ans += (ll)N * cntN;

    cout << ans << '\n';
    return 0;
}