//#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 = 1000;
int L[D*2+1], R[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] = R[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++;
        }
        for (int i=p+1,B=D;;i++)
        {
            if (B==0 or B==2*D) break;
            R[B]++;
            if (i==n) break;
            if (a[i]<a[p]) B--;
            else B++;
        }
        for (int w=1;w<2*D;w++)
        {
            A += L[w]*1LL*R[2*D-w]*a[p];
            A += L[w]*1LL*R[2*D-w+1]*a[p];
        }
    }
    cout << A << "\n";
}


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