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

int n;
int a[5005];

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]);
	int s=0;
	while(!check()){
		int mn=1e9,p1=0,p2=0;
		for(int i=1;i<=n;i++)
			if(mn>a[i]) mn=a[i],p1=i;
		for(int i=p1;i<=n;i++)
			if(a[i]==mn) p2=i;
		int x=min(a[p1-1],a[p2+1]);
		(s+=((x-mn)*(a[p1-1]+a[p2+1])%mod+(mn+x-1)*(x-mn)/2%mod)%mod*(p2-p1+1)%mod)%=mod;
		for(int i=p1;i<=p2;i++) a[i]=x;
	}
	printf("%d\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
*/