#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000003
const int N = 1000005;
ll n, h[N], pref[N], suff[N], tar[N];
vector<int> ord;
int sm(int l, int r)
{
return (l + r) * (r - l + 1) / 2 % MOD;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> h[i];
ord.push_back(h[i]);
}
for (int i = 1; i <= n; i++)
{
pref[i] = max(pref[i - 1], h[i]);
}
for (int i = n; i >= 1; i--)
{
suff[i] = max(suff[i + 1], h[i]);
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
tar[i] = min(pref[i], suff[i]);
ans = (ans + sm(h[i], tar[i] - 1)) % MOD;
}
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
ll last = 0;
for (int j : ord)
{
ll ok = 0, mn = 1e10, cnt = 0;
for (int i = 1; i <= n; ++i)
{
if (tar[i] >= j and h[i] < j)
{
if (!ok)
{
ans = (ans + (mn * (j - last)) % MOD) % MOD;
}
ok = 1;
cnt++;
}
if (h[i] >= j)
{
mn = min(mn, h[i]);
}
}
ok = 0, mn = 1e10;
for (int i = n; i >= 1; i--)
{
if (tar[i] >= j and h[i] < j)
{
if (!ok)
{
ans = (ans + (mn * (j - last)) % MOD) % MOD;
}
else
{
ans = (ans + sm(last + 1, j)) % MOD;
}
ok = 1;
}
if (h[i] >= j)
{
mn = min(mn, h[i]);
}
}
if (cnt == 2)
{
ans = (ans + (mn * (j - last))) % MOD;
}
last = j;
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t = 1;
// cin >> t;
for (int i = 1; i <= t; i++)
{
solve();
}
}
