#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define int long long

const int mod = ;

#define add(x,y) x=(x+y)%mod

#define del(x,y) (x-y+mod)%mod

inline int lb(int x){return x&(-x);}

int a[],b[],sum1[],sum2[],h[],n,m;

inline void add_a(int x,int k){while(x<=m)add(a[x],k),x+=lb(x);return;}

inline void add_b(int x,int k){while(x<=m)add(b[x],k),x+=lb(x);return;}

inline int q_a(int x){int res=;while(x)add(res,a[x]),x-=lb(x);return res;}

inline int q_b(int x){int res=;while(x)add(res,b[x]),x-=lb(x);return res;}

signed main(){

    int i,j,k;

    scanf("%lld",&n);

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

      scanf("%lld",&h[i]);

      m=max(m,h[i]);

    }

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

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

      add_a(h[i],);

      add_b(h[i],del(q_a(m),q_a(h[i])));

      sum1[i]=q_b(h[i]-);

    }

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(i=n;i>;i--){

      add_a(h[i],);

      add_b(h[i],del(q_a(m),q_a(h[i])));

      sum2[i]=q_b(h[i]-);

    }

    int ans=;

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

      ans=(ans+1ll*sum1[i]*sum2[i]%mod)%mod;

    cout<<ans<<"\n";

    return ;

}