#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b)
{
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b)
{
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b)
{
    return 1ll * a * b % mod;
}

int bp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x)
{
    return bp(x, mod - 2);
}

int n, p[N], pp[N];
ll ans;

struct kek
{
    int sum;
    int mn_pre, mx_pre;
    int mn_suf, mx_suf;

    kek()
    {
        sum = 0;
        mn_pre = 0;
        mx_pre = 0;
        mn_suf = 0;
        mx_suf = 0;
    }

    kek(int x)
    {
        sum = x;
        mn_pre = min(x, 0);
        mx_pre = max(x, 0);
        mn_suf = min(x, 0);
        mx_suf = max(x, 0);
    }

    kek operator+(const kek &other) const
    {
        kek res;
        res.sum = sum + other.sum;
        res.mn_pre = min(mn_pre, other.mn_pre + sum);
        res.mx_pre = max(mx_pre, other.mx_pre + sum);

        res.mn_suf = min(mn_suf + other.sum, other.mn_suf);
        res.mx_suf = max(mx_suf + other.sum, other.mx_suf);

        return res;
    }
} t[N << 2], PRE, SUF;

ll cur;
int add;
int was[2 * N], cnt[2 * N], timer;

void upd(int v, int tl, int tr, int p, int x)
{
    if (tl == tr)
    {
        t[v] = kek(x);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        upd(v << 1, tl, tm, p, x);
    else
        upd(v << 1 | 1, tm + 1, tr, p, x);
    t[v] = t[v << 1] + t[v << 1 | 1];
}

kek get(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l || l > r)
        return kek();
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) >> 1;
    return get(v << 1, tl, tm, l, r) + get(v << 1 | 1, tm + 1, tr, l, r);
}

bool check(int al, int ar, int bl, int br)
{
    // cerr << al << " " << ar << "  " << bl << " " << br << endl;
    return al + bl <= 2 && -2 <= ar + br;
}

void work_pre(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l || l > r)
        return;
    if (l <= tl && tr <= r && !check(t[v].mn_suf + add, t[v].mx_suf + add, SUF.mn_pre, SUF.mx_pre))
    {
        add += t[v].sum;
        return;
    }
    if (tl == tr)
    {
        add += t[v].sum;
        // cerr << add << endl;
        int x = N - add;
        if (was[x] != timer)
            was[x] = timer, cnt[x] = 0;
        cnt[x]++;
        return;
    }

    int tm = (tl + tr) >> 1;

    work_pre(v << 1 | 1, tm + 1, tr, l, r);

    work_pre(v << 1, tl, tm, l, r);
}

void work_suf(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l || l > r)
        return;
    if (l <= tl && tr <= r && !check(t[v].mn_pre + add, t[v].mx_pre + add, PRE.mn_suf, PRE.mx_suf))
    {
        add += t[v].sum;
        return;
    }

    if (tl == tr)
    {
        add += t[v].sum;
        // cerr << add << endl;
        int x = N + add;
        if (was[x] != timer)
            was[x] = timer, cnt[x] = 0;
        cur += cnt[x];
        x--;
        if (was[x] != timer)
            was[x] = timer, cnt[x] = 0;
        cur += cnt[x];
        return;
    }

    int tm = (tl + tr) >> 1;

    work_suf(v << 1, tl, tm, l, r);

    work_suf(v << 1 | 1, tm + 1, tr, l, r);
}

mt19937 rnd(353);

void solve()
{
    // cin >> n;
    n = 300000;
    iota(p, p + n, 0);
    shuffle(p, p + n, rnd);
    for (int i = 0; i < n; i++)
    {
        // cin >> p[i];
        // p[i]--;
        pp[p[i]] = i;
    }
    for (int i = 0; i < n; i++)
        upd(1, 0, n - 1, i, 1);
    for (int i = 0; i < n; i++)
    {
        // cerr << "G  " << i << endl << endl;
        upd(1, 0, n - 1, pp[i], 0);

        PRE = get(1, 0, n - 1, 0, pp[i]);
        SUF = get(1, 0, n - 1, pp[i], n - 1);
        cur = 0;
        timer++;
        add = 0;
        work_pre(1, 0, n - 1, 0, pp[i]);
        add = 0;
        work_suf(1, 0, n - 1, pp[i], n - 1);

        // cerr << cur << endl;
        ans += 1ll * cur * (i + 1);
        upd(1, 0, n - 1, pp[i], -1);

        // exit(0);
    }
    cout << ans << "\n";
    return;
    const int D = 1000;
    ll L[D * 2 + 1];
    int a[N];
    for (int i = 0; i < n; i++)
        a[i] = p[i] + 1;
    ll A = 0;
    for (int p = 0; p < n; p++)
    {
        for (int w = 0; w <= 2 * D; w++)
            L[w] = 0;
        for (int i = p - 1, B = D;; i--)
        {
            if (B == 0 or B == 2 * D)
                break;
            L[B]++;
            if (i == -1)
                break;
            if (a[i] < a[p])
                B--;
            else
                B++;
        }
        int S = 0;
        for (int j = 2 * D - 1; j >= 0; j--)
            L[j + 1] += L[j];
        for (int i = p + 1, B = D + 1;; i++)
        {
            if (B == 0 or B == 2 * D)
                break;
            S += L[B];
            if (i == n)
                break;
            if (a[i] < a[p])
                B++;
            else
                B--;
        }
        A += S * 1LL * a[p];
    }
    cout << A << "\n";
}

int main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << endl;
        solve();
    }
}