#include <bits/stdc++.h>
using namespace std; 
const int N = 1e6 + 5; 
const int P = 1e6 + 3; 
const int INF = 1e9 + 1; 

int S(int l, int r) { return 1ll * (l + r) * (r - l + 1) / 2 % P; }
int n, h[N], pre[N], suf[N];  
int C[N]; 
void add(int x, int k) { for (; x <= n; x += x & -x) C[x] += k; }
int sum(int x) { int r = 0; for (; x; x -= x & -x) r += C[x]; return r; }
int kth(int k) {
    int x = 0, s = 0; 
    for (int i = 19; i >= 0; --i) {
        x += 1 << i; 
        if (x >= n || s + C[x] >= k) x -= 1 << i; 
        else s += C[x]; 
    }
    return x + 1; 
}

int T[N * 4]; 
void build(int o, int l, int r) {
    if (l == r) return T[o] = h[l], void(); 
    int mid = l + r >> 1; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 
    T[o] = min(T[o << 1], T[o << 1 | 1]); 
}
void update(int o, int l, int r, int x) {
    if (l == r) return T[o] = INF, void(); 
    int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x); 
    else update(o << 1 | 1, mid + 1, r, x); 
    T[o] = min(T[o << 1], T[o << 1 | 1]); 
}
int qmin(int o, int l, int r, int x, int y) {
    if (x > y) return 0; 
    if (x <= l && r <= y) return T[o]; 
    int mid = l + r >> 1, res = INF; 
    if (x <= mid) res = qmin(o << 1, l, mid, x, y); 
    if (mid < y) res = min(res, qmin(o << 1 | 1, mid + 1, r, x, y)); 
    return res; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> h[i], pre[i] = max(pre[i - 1], h[i]); 
    for (int i = n; i >= 1; --i) suf[i] = max(suf[i + 1], h[i]); 
    build(1, 1, n); 

    vector<pair<int, int>> vec; 
    for (int i = 1; i <= n; ++i) vec.emplace_back(h[i], i); 

    sort(vec.begin(), vec.end()); int mx = vec.back().first; 
    int l = 1, r = n, ans = 0; 
    for (int op = 0; op < vec.size(); ++op) {
        int val = vec[op].first; 
        if (val == mx) break; 
        add(vec[op].second, 1); update(1, 1, n, vec[op].second); 
        if (val == vec[op + 1].first) continue; 

        while (pre[l] <= val) add(l++, -1); 
        while (suf[r] <= val) add(r--, -1); 
        int cnt = sum(n); 
        if (cnt == 0) continue; 
        if (cnt == 1) {
            int pos = kth(1); 
            int vl = qmin(1, 1, n, 1, pos - 1), vr = qmin(1, 1, n, pos + 1, n); 
            ans = (ans + 1ll * (vl + vr) * (vec[op + 1].first - val)) % P; 
            ans = (ans + S(val, vec[op + 1].first - 1)) % P; 
            continue; 
        }
        int x = kth(1), y = kth(cnt); 
        int vl = qmin(1, 1, n, 1, x - 1), vr = qmin(1, 1, n, y + 1, n); 

        int c = (0ll + vl + vr + min(vl, vr)) % P; // 
        ans = (ans + 1ll * c * (vec[op + 1].first - val)) % P; 
        c = cnt; // 每个自己
        ans = (ans + 1ll * c * S(val, vec[op + 1].first - 1)) % P; 
        c = (2 * (cnt - 2) + 1) % P; 
        // 中间对应的两边，两边的一个对应的一个，之前算过中间对应的两边和两边对应的一个是 +1 贡献的等差数列
        ans = (ans + 1ll * c * S(val + 1, vec[op + 1].first)) % P; 
    }
    cout << ans << '\n'; 
    return 0; 
}