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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }
//

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}
void read_cr() {
    fgets(_buf, 256, stdin);
}


ll naive(int N, vi& a) {
    ll ans = 0LL;
    for (int l=0; l<N; ++l) {
        for (int r=l; r<N; ++r) {
            int minv = INT_MAX;
            for (int i=l; i<=r; ++i) {
                minv = min(minv, a[i]);
            }
            ans += minv;
        }
    }
    return ans;
}


inline ll f(int n) {
    // nC2
    return (ll)n*(n+1)/2;
}

ll fast(int N, vi& a) {
    ll ans = 0LL;
    // 区間数は1+2+..+N =N(N+1)/2
    // 1から順に、その数がminになるのが何回あるか数える？
    // 1有り範囲: [0 .. N) =
    // 1なし2有り範囲:  [) 1の位置 [)
    // 区間長n -> f(n)=n(n+1)/2
    // kで長さaの区間がa1,a2に分割されたとき(a=a1+a2+1)
    // kを含んでいた頃：f(a) これはminがk+1以上を含む
    // kを含まない頃 (minがk+1): f(a1)+f(a2)
    // 1つの数字の出現で高々1回しかsplitは発生しない
    // ... 20万回分割していくと?
    // 後でNから逆に包含を溶いていく？
    vector<ii> b(N);
    rep(i,N) b[i] = ii(a[i], i);
    sort(ALL(b)); // (1,w)...(N,w)
    vi aR(N+1);
    rep(i,N) aR[1+i] = b[i].second;
    aR[0] = -1;//
#ifdef DEBUG
    cerr << "aR: " << aR << endl;
#endif
    vector<ll> pat(N+1);
    pat[0] = f(N);

    set<ii> spans;
    spans.insert(ii(0,N)); // (from, len)
#ifdef DEBUG
    cerr << 0 << spans << endl;
#endif

    for (int x=1; x<=N; ++x) { // 200000
        int at = aR[x];
#ifdef DEBUG
        fprintf(stderr, "x=%d, at=%d", x, at); cerr << spans << endl;
#endif
        // if (spans.empty()) {
        //     break;
        // }

        auto it = spans.lower_bound(ii(at,N+1));
        assert(it != spans.begin());
        --it;

        int from = it->first, len = it->second;
        spans.erase(it);
        pat[x] = f(len);
        // [from, at), at, [at+1, from+len)
        if (from != at) {
            int sub_len = at - from;
            spans.insert(ii(from, sub_len));
            pat[x] -= f(sub_len);
        }
        if (at != from+len-1) {
            int sub_len = (from+len) - (at+1);
            spans.insert(ii(at+1, sub_len));
            pat[x] -= f(sub_len);
        }
        ans += (ll)x * pat[x];
#ifdef DEBUG
        cerr << x << spans << endl;
#endif
    }

    // ll patR(N+1, 0);
    // patR[n] = pat[n];
    // for (int i=N-1; i>=0; --i) {
    //     patR[i] = patR[i+1]
    // }

#ifdef DEBUG
    cerr << "pat:" << pat << endl;
#endif
    return ans;
}

ll solve(int N, vi& a) {
    ll ans = fast(N,a);
    // if (N < 100) {
    //     ll naive_ans = naive(N,a);
    //     assert(ans == naive_ans);
    // }
    return ans;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << solve(N,a) << endl;
    // cout << (solve(N,a) ? "Yes":"No") << endl;
    return 0;
}


Measured memory_bytes: 8576