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

int n;
int a[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;
}

inline void init(){
	int l=1,r=n;
	for(int i=2;i<=n;i++)
		if(a[i]>=a[i-1]) l=i;
		else break;
	for(int i=n-1;i>=1;i--)
		if(a[i]>=a[i+1]) r=i;
		else break;
	if(l>r){puts("0");exit(0);}
	n=r-l+1;
	for(int i=1;i<=n;i++) b[i]=a[i+l-1];
	for(int i=1;i<=n;i++) a[i]=b[i];

	return ;
}

int main(){
	// freopen("repair.in","r",stdin);
	// freopen("repair.out","w",stdout);
	in(n);
	for(int i=1;i<=n;i++) in(a[i]);
	init();
	ll 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=1;i<=n;i++)
			if(a[i]==mn) p2=i;
		ll s1=0,s2=0;
		int m1=1e9,m2=1e9;
		for(int i=1;i<p1;i++)
			if(a[i]>mn) m1=min(m1,a[i]);
		for(int i=p1+1;i<=n;i++)
			if(a[i]>mn) m2=min(m2,a[i]);
		if(p1==p2){
			a[p1]++;
			(s+=mn+m1+m2)%=mod;
			continue;
		}
		s1=mn+m1+m2;
		m1=mn+1,m2=1e9;
		for(int i=p2+1;i<=n;i++) 
			if(a[i]>mn) m2=min(m2,a[i]);
		s1+=mn+m1+m2;
		m1=1e9,m2=1e9;
		for(int i=1;i<p2;i++)
			if(a[i]>mn) m1=min(m1,a[i]);
		for(int i=p2+1;i<=n;i++)
			if(a[i]>mn) m2=min(m2,a[i]);
		s2+=mn+m1+m2;
		m1=1e9,m2=mn+1;
		for(int i=1;i<p1;i++) 
			if(a[i]>mn) m1=min(m1,a[i]);
		s2+=mn+m1+m2;
		(s+=min(s1,s2))%=mod;
		int tt=0;
		for(int i=1;i<=n;i++)
			if(a[i]==mn) a[i]++,tt++;
		tt-=2;
		(s+=tt*(mn*3+2)%mod)%=mod;
	}
	printf("%lld\n",s);

	return 0;
}
/*
10
72 33 22 22 13 49 53 57 72 85
*/