//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pii pair<int,int>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

struct edge{

    int u,v,ma,mi;

}e[N];

int father[N],sz[N],val[N];

int Find(int x)

{

    return father[x]==x?x:father[x]=Find(father[x]);

}

bool cmp1(edge a,edge b)

{

    return max(val[a.u],val[a.v])<max(val[b.u],val[b.v]);

}

bool cmp2(edge a,edge b)

{

    return min(val[a.u],val[a.v])>min(val[b.u],val[b.v]);

}

int main()

{

    int n,cnt=;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&val[i]);

        if(i>)

        {

            e[cnt].u=i-,e[cnt].v=i;

            cnt++;

        }

        father[i]=i,sz[i]=;

    }

    sort(e,e+cnt,cmp1);

//    for(int i=0;i<cnt;i++)

//        printf("%d %d\n",e[i].u,e[i].v);

    ll ans=;

    for(int i=;i<cnt;i++)

    {

        int x=Find(e[i].u),y=Find(e[i].v);

        if(x!=y)

        {

            ans+=(ll)sz[x]*sz[y]*max(val[e[i].u],val[e[i].v]);

            father[x]=y,sz[y]+=sz[x];

        }

    }

    for(int i=;i<=n;i++)father[i]=i,sz[i]=;

    sort(e,e+cnt,cmp2);

    for(int i=;i<cnt;i++)

    {

        int x=Find(e[i].u),y=Find(e[i].v);

        if(x!=y)

        {

            ans-=(ll)sz[x]*sz[y]*min(val[e[i].u],val[e[i].v]);

            father[x]=y,sz[y]+=sz[x];

        }

    }

    printf("%lld\n",ans);

    return ;

}

/********************

********************/