#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18,siz=1048576,mod=1000003;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],seg[2200000],num,b[1100000];
set<ll> st;
vector<ll> u;
vector<pair<ll,ll>> v[1100000];
ll lb(ll x)
{
    return lower_bound(u.begin(),u.end(),x)-u.begin();
}
void f(ll x)
{
    seg[x]=min(seg[x*2],seg[x*2+1]);
    if(x==1)
        return;
    f(x/2);
}
ll g(ll x,ll y,ll z)
{
    if(l>y||x>r)
        return inf;
        if(l<=x&&y<=r)
            return seg[z];
        return min(g(x,(x+y)/2,z*2),g((x+y)/2+1,y,z*2+1));
}
ll sum(ll x,ll y)
{
    return y*(y+1)/2-x*(x-1)/2;
}
ll find_smallest(ll x,ll y)
{
    l=x;
    r=y;
    return g(1,siz,1);
}
int main()
{
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    s=0;
    r=0;
    for(i=1;i<=n;i++)
    {
        if(a[i]>=s)
        {
            s=a[i];
            r=i;
        }
    }
    s=0;
    l=0;
    for(i=n;i>=1;i--)
    {
        if(a[i]>=s)
        {
            s=a[i];
            l=i;
        }
    }
    s=0;
    for(i=1;i<=r;i++)
    {
        s=max(s,a[i]);
        b[i]=s;
    }
    s=0;
    for(i=n;i>=l;i--)
    {
        s=max(s,a[i]);
        b[i]=s;
    }
    /*for(i=1;i<=n;i++)
        printf("%lld ",b[i]);
    printf("\n");
    */s=0;
    for(i=1;i<=n;i++)
    {
        u.push_back(a[i]);
        u.push_back(b[i]);
        seg[i+siz-1]=a[i];
        f((i+siz-1)/2);
        s+=sum(a[i],b[i]-1);
        s%=mod;
    }
    //printf("(%lld)\n",s);
    sort(u.begin(),u.end());
    u.erase(unique(u.begin(),u.end()),u.end());
    for(i=1;i<=n;i++)
    {
        /*if(a[i]==b[i])
            continue;
        */v[lb(a[i])].push_back({1,i});
        v[lb(b[i])].push_back({0,i});
    }
    num=0;
    for(i=0;i<ll(u.size())-1;i++)
    {
        for(auto p:v[i])
        {
            x=p.first;
            y=p.second;
            if(x)
            {
                num++;
                st.insert(y);
                seg[y+siz-1]=inf;
                f((y+siz-1)/2);
            }
            else
            {
                num--;
                st.erase(y);
            }
        }
        if(st.empty())
            continue;
        l=(*st.begin());
        r=(*(--st.end()));
        if(l==r)
        {
            z=0;
        z+=find_smallest(1,l-1);
        z+=find_smallest(r+1,n);
        //printf("(%lld->%lld:%lld)\n",u[i],u[i+1],z*(u[i+1]-u[i]));
        s+=z*(u[i+1]-u[i]);
        s%=mod;
            continue;
        }
        z=0;
        z+=find_smallest(1,l-1);
        z+=find_smallest(r+1,n);
        z+=min(find_smallest(l+1,n),find_smallest(1,r-1));
        z*=(u[i+1]-u[i]);
        //printf("(%lld->%lld:%lld)\n",u[i],u[i+1],z+(2*num-3)*sum(u[i]+1,u[i+1]));
        s+=z+(2*num-3)*sum(u[i]+1,u[i+1]);
        s%=mod;
    }
    s%=mod;
    printf("%lld",s);
}