#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>

#define int long long

using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
const ll MOD = 1e6 + 3;

int c[N], n, a[N], b[N], tot, premx[N], sufmx[N];
ll ans, inv2;
vector <int> G1[N];

ll power(ll a, ll b)
{
	ll c = 1;
	while(b)
	{
		if(b & 1) c = c * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return c;
}

int read()
{
	int x = 0, t = 1; char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') t = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * t;
}

int val(int x)
{
	return lower_bound(b + 1, b + tot + 1, x) - b;
}


void add(int x, int y)
{
	for(; x <= n; x += x & -x) c[x] += y;
}

int ask(int x)
{
	int res = 0;
	for(; x; x -= x & -x) res += c[x];
	return res;
}

namespace s1{
	struct SegmentTree{
		int l, r, mn;
	}tr[N << 2];
	
	void pushup(int p)
	{
		tr[p].mn = min(tr[p << 1].mn, tr[p << 1 | 1].mn);
	}
	
	void build(int p, int l, int r)
	{
		tr[p].l = l, tr[p].r = r;
		if(l == r)
		{
			tr[p].mn = a[l];
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void change(int p, int x)
	{
		if(tr[p].l == tr[p].r)
		{
			tr[p].mn = tot + 1;
			return;
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(x <= mid) change(p << 1, x);
		else change(p << 1 | 1, x);
		pushup(p);
	}
	
	int query(int p, int x, int y)
	{
		if(x <= tr[p].l && tr[p].r <= y) return tr[p].mn;
		int mid = tr[p].l + tr[p].r >> 1, res = tot + 1;
		if(x <= mid) res = min(res, query(p << 1, x, y));
		if(y > mid) res = min(res, query(p << 1 | 1, x, y));
		return res;
	}
}

namespace s2{
	struct SegmentTree{
		int l, r, mx, mn;
	}tr[N << 2];
	
	void pushup(int p)
	{
		tr[p].mn = min(tr[p << 1].mn, tr[p << 1 | 1].mn);
		tr[p].mx = max(tr[p << 1].mx, tr[p << 1 | 1].mx);
	}
	
	void build(int p, int l, int r)
	{
		tr[p].l = l, tr[p].r = r;
		if(l == r)
		{
			tr[p].mx = -1, tr[p].mn = n + 1;
			return;
		}
		int mid = l + r >> 1;
		build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
		pushup(p);
	}
	void change(int p, int x)
	{
		if(tr[p].l == tr[p].r)
		{
			tr[p].mx = tr[p].mn = x;
			return;
		}
		int mid = tr[p].l + tr[p].r >> 1;
		if(x <= mid) change(p << 1, x);
		else change(p << 1 | 1, x);
		pushup(p);
	}
	
	int querymn(int p, int x, int y)
	{
		if(x <= tr[p].l && tr[p].r <= y) return tr[p].mn;
		int mid = tr[p].l + tr[p].r >> 1, res = n + 1;
		if(x <= mid) res = min(res, querymn(p << 1, x, y));
		if(y > mid) res = min(res, querymn(p << 1 | 1, x, y));
		return res;
	}
	
	int querymx(int p, int x, int y)
	{
		if(x <= tr[p].l && tr[p].r <= y) return tr[p].mx;
		int mid = tr[p].l + tr[p].r >> 1, res = -1;
		if(x <= mid) res = max(res, querymx(p << 1, x, y));
		if(y > mid) res = max(res, querymx(p << 1 | 1, x, y));
		return res;
	}
}


signed main()
{
	freopen("data.in", "r", stdin);
	//freopen("data.out", "w", stdout);
	inv2 = power(2, MOD - 2);
	n = read();
	for(int i = 1; i <= n; i++) b[++tot] = a[i] = read();
	sort(b + 1, b + tot + 1);
	tot = unique(b + 1, b + tot + 1) - b - 1;
	for(int i = 1; i <= n; i++)
	{
		a[i] = val(a[i]);
		G1[a[i]].push_back(i);
	}
	for(int i = 1; i <= n; i++) premx[i] = max(premx[i - 1], a[i]);
	for(int i = n; i; i--) sufmx[i] = max(sufmx[i + 1], a[i]);
	s1::build(1, 1, n), s2::build(1, 1, n);
	reverse(sufmx + 1, sufmx + n + 1);
	for(int i = 1; i < tot; i++)
	{
		for(auto& pos : G1[i]) add(pos, 1), s1::change(1, pos), s2::change(1, pos);
		int L = lower_bound(premx + 1, premx + n + 1, i + 1) - premx, R = n - (lower_bound(sufmx + 1, sufmx + n + 1, i + 1) - sufmx) + 1;
		if(L > R) continue;
		int l = s2::querymn(1, L, R), r = s2::querymx(1, L, R);
		int cnt = ask(R) - ask(L - 1);
		if(!cnt) continue;
		if(cnt == 1)
		{
			ans = (ans + (ll)(b[s1::query(1, 1, l - 1)] + b[s1::query(1, r + 1, n)]) % MOD * (b[i + 1] - b[i]) % MOD) % MOD;
			ans = (ans + (ll)(b[i] + b[i + 1] - 1) % MOD * (b[i + 1] - b[i]) % MOD * inv2) % MOD;
		}
		else
		{
			int v1 = b[s1::query(1, 1, l - 1)], v2 = b[s1::query(1, 1, r - 1)], v3 = b[s1::query(1, l + 1, n)], v4 = b[s1::query(1, r + 1, n)];
			ans = (ans + (ll)(v1 + v2 + v3 + v4 - max(v2, v3)) % MOD * (ll)(b[i + 1] - b[i]) % MOD) % MOD;
			ans = (ans + (ll)(b[i] + b[i + 1] - 1) % MOD * (ll)(b[i + 1] - b[i]) % MOD * 3ll % MOD * inv2 % MOD) % MOD;
			ans = (ans + (ll)(b[i + 1] - b[i]) % MOD) % MOD;
			ans = (ans + (ll)(cnt - 2) % MOD * (3ll * b[i] + 2 + 3ll * b[i + 1] - 1) % MOD * (ll)(b[i + 1] - b[i]) % MOD * inv2 % MOD) % MOD;
		}
	}
	printf("%lld\n", ans);
	return 0;
}