#include <bits/stdc++.h>
#define MAX 100005
#define ll long long
using namespace std;

const int MOD = 1000000000;

struct ma{
    ll vt, old, nw;
};

ll s[MAX], c[MAX], kq;
ma a[MAX], b[MAX];
int n;

bool cmp(ma a, ma b)
{
    return a.old<b.old;
}

void Init()
{
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> b[i].old;
        b[i].vt=i;
    }
    sort(b+1,b+n+1, cmp);
    int dem=0;
    for (int i=1; i<=n; i++)
    {
        if (b[i].old!=b[i-1].old) dem++;
        b[i].nw=dem;
    }
    for (int i=1; i<=n; i++)
    {
        a[b[i].vt]=b[i];
    }
}

ll get1(int x)
{
    ll k=0;
    for (; x>0; x&= (x-1))
        k+=c[x];
    return k;
}

ll get2(int x)
{
    ll k=0;
    for (; x>0; x&=(x-1))
       {
            k+=s[x];
           k%=MOD;
       }
    return k;
}

void update1(int x)
{
    for (; x<=MAX; x+= x& -x)
        c[x]++;
}
void update2(int x, int t)
{
    for (; x<=MAX; x+= x& -x)
        s[x]+=t;
}

void Solve()
{
    for (int i=n; i>0; i--)
    {
        kq+= a[i].old * get1(a[i].nw) - get2(a[i].nw);
        kq%=MOD;
        update1(a[i].nw+1);
        update2(a[i].nw+1, a[i].old);
    }
    cout<<kq;
}



int main()
{
    Init();
    Solve();
    return 0;
}