#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);
constexpr ll mod = 1e6+3;

int main(){
    cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll N; cin >> N;
    vi H(N);
    rep(i,0,N) cin >> H[i];
    vi goal(N,inf);
    ll max = 0;
    rep(i,0,N){
        max = std::max(max, H[i]);
        goal[i] = std::min(goal[i], max);
    }
    max = 0;
    per(i,N-1,0){
        max = std::max(max, H[i]);
        goal[i] = std::min(goal[i], max);
    }
    rep(i,0,N) cout << goal[i] << " ";
    cout << ln;
    ll ans = 0;
    rep(i,0,N){
        ans += (goal[i]-1+H[i])*(goal[i]-H[i])/2;
        ans %= mod;
    }
    std::set<ll> set;
    rep(i,0,N){
        set.insert(H[i]);
        ll now = H[i];
        for(auto el: set){
            if(el >= now){
                ans += (std::min(el, goal[i])-now)*el;
                ans %= mod;
                now = std::min(el, goal[i]);
            }
        }
    }
    set.clear();
    per(i,N-1,0){
        set.insert(H[i]);
        ll now = H[i];
        for(auto el: set){
            if(el >= now){
                ans += (std::min(el, goal[i])-now)*el;
                ans %= mod;
                now = std::min(el, goal[i]);
            }
        }
    }
    cout << ans << ln;
}