#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000003
#define ll long long
using namespace std;

int n;
int a[1000005];
int a1[1000005];
int a2[1000005];
int b[1000005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

inline bool check(){
	int mx=0,ps=0;
	for(int i=1;i<=n;i++)
		if(mx<a[i]) mx=a[i],ps=i;
	for(int i=ps;i>=1;i--)
		if(a[i]<a[i-1]) return false;
	for(int i=ps;i<n;i++)
		if(a[i]<a[i+1]) return false;
	return true;
}

int main(){
	// freopen("repair.in","r",stdin);
	// freopen("repair.out","w",stdout);
	in(n);
	for(int i=1;i<=n;i++) in(a[i]);
	ll s=0;
	while(!check()){
		int mn=1e9,ps=0,t1=0,t2=0;
		for(int i=1;i<=n;i++)
			if(mn>a[i]) mn=a[i],ps=i;
		for(int i=1;i<ps;i++) a1[++t1]=a[i];
		for(int i=ps+1;i<=n;i++) a2[++t2]=a[i];
		sort(a1+1,a1+1+t1);
		sort(a2+1,a2+1+t2);
		int l=1,r=1;
		while(l<=t1&&r<=t2){
			int x=min(a1[l],a2[r]);
			(s+=1ll*(x-mn)%mod*(a1[l]+a2[r])%mod+1ll*(mn+x-1)*(x-mn)/2%mod)%=mod;
			mn=x;
			if(x==a1[l]) l++;
			if(x==a2[r]) r++;
		}
		int tt=0;
		for(int i=1;i<ps;i++) b[++tt]=a[i];
		for(int i=ps+1;i<=n;i++) b[++tt]=a[i];
		n=tt;
		for(int i=1;i<=n;i++) a[i]=b[i];
	}
	printf("%lld\n",s);

	return 0;
}
/*
8
8 8 6 3 1 2 5 7

8 8 6 3 1 2 5 7
(3,1,2)
8 8 6 3 2 2 5 7
(3,2,5)*2
8 8 6 3 3 3 5 7
(6,3,5)*3
(6,4,5)*3
8 8 6 5 5 5 5 7
(6,5,7)*4
8 8 6 6 6 6 6 7
(8,6,7)*5
8 8 7 7 7 7 7 7
*/