//#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define X first
#define Y second


const ll mod = 1000000007;
//const ll mod = 998244353;


const int D = 800;
ll L[D*2+1];

mt19937 gen(353);

void solve()
{
    int n = 300000;
    //cin >> n;
    vector<int> a(n);
    for (int i=0;i<n;i++)
    {
        a[i] = i+1;
        //cin >> a[i];
    }
    shuffle(a.begin(),a.end(),gen);
    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";
    //6746525300825836
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}