//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
#define int long long
int mod = 1e6 + 3;
struct segtree {
    int sz;
    vector<int> tree;
    void make(vector<int> a) {
        sz = 1;
        while (sz < a.size())
            sz *= 2;
        tree.assign(sz * 2, {});
        for (int i = 0; i < a.size(); ++i) {
            tree[i + sz] = a[i];
        }
        for (int i = sz-1; i > 0; --i) {
            tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
        }
    }
    void ch(int v) {
        v += sz;
        tree[v] = 1e15;
        while (v != 1) {
            v /= 2;
            tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
        }
    }
    int get(int l, int r) {
        //cerr << l << ' ' << r << ' ' << sz << endl;
        l += sz;
        r += sz;
        int res = 1e15;
        while (l <= r) {
            if (l % 2 == 1) {
                res = min(res, tree[l]);l++;
            }
            if (r % 2 == 0) {
                res = min(res, tree[r]);r--;
            }
            l /= 2;r /= 2;
        }
        return res;
    }
};
int calcsum(int l, int r) {
    //int rs = 0;
    //for (int i = l; i <= r; ++i) {
    //    rs += i;
    //}
    //return rs % mod;
    return (r * (r + 1) / 2 - l * (l - 1) / 2) % mod;
}
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<pair<int, int>> indsr(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        indsr[i] = {a[i], i};
    }
    sort(all(indsr));
    segtree sg;
    sg.make(a);
    int reska = 0;
    set<int> corel;
    int corval = 0;
    for (int i = 0; i < indsr.size(); ++i) {
        sg.ch(indsr[i].second);
        if (i + 1 != indsr.size() and indsr[i].first == indsr[i + 1].first) {
            corel.insert(indsr[i].second);
        } else {
            corel.insert(indsr[i].second);
            int lvl = 0, rvl = 0;
            while (!corel.empty()) {
                int x = *corel.begin();
                int vl = sg.get(0, x - 1);
                if (vl > 1e10)
                    corel.erase(x);
                else {
                    lvl = vl;
                    break;
                }
            }
            while (!corel.empty()) {
              //  cout << "FISH" << endl;
                int x = *corel.rbegin();
                int vl = sg.get(x+1, a.size() - 1);
                if (vl > 1e10)
                    corel.erase(x);
                else {
                    rvl = vl;
                    break;
                }
            }
            //cout << "FISHA" << endl;
            int sz = corel.size();
            if (sz == 0)
                continue;
            pair<int, int> stpprc;
            if (sz == 1)
                stpprc = {lvl + rvl, 1};
            else
                stpprc = {min(lvl, rvl) * 2 + max(lvl, rvl) + sz * 3 - 3 - sz, sz * 3 - 3};
            int mvtrg = indsr[i + 1].first - indsr[i].first;
            //cout << mvtrg << ' ' << sz << ' ' << stpprc.first << ' ' << stpprc.second << '\n';
            reska += stpprc.first % mod * mvtrg % mod;
            reska += calcsum(indsr[i].first, indsr[i + 1].first - 1) * stpprc.second % mod;
        }
    }
    reska %= mod;
    cout << reska << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}