#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MOD = 1e6 + 3;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> h(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    ll best = 3e18;
    int p = max_element(h.begin(), h.end()) - h.begin();

    vector<bool> used(n);
    ll ans = 0;
    int f = 0;
    while (count(used.begin(), used.end(), false)) {
        int i = -1;
        if (f == 0) {
            for (int j = 0; j < n; ++j) {
                if (!used[j] && (i == -1 || h[i] > h[j])) {
                    i = j;
                }
            }
        } else {
            for (int j = n - 1; j >= 0; --j) {
                if (!used[j] && (i == -1 || h[i] > h[j])) {
                    i = j;
                }
            }
        }
        bool ok = false;
        if (i <= p) {
            if (*max_element(h.begin(), h.begin() + i + 1) == h[i]) {
                ok = true;
            }
        }
        if (i >= p) {
            if (*max_element(h.begin() + i, h.end()) == h[i]) {
                ok = true;
            }
        }
        if (ok) {
            used[i] = true;
            continue;
        }
        f ^= 1;
        int l = 1e9, r = 1e9;
        for (int j = 0; j < i; ++j) {
            if (h[j] > h[i]) {
                l = min(l, h[j]);
            }
        }
        for (int j = i + 1; j < n; ++j) {
            if (h[j] > h[i]) {
                r = min(r, h[j]);
            }
        }
        ans = ans + l + r + h[i];
        h[i] += 1;
    }

    for (int x : h) {
        cout << x << " ";
    }
    cout << '\n';

    best = min(best, ans);

    cout << best % MOD << '\n';

    return 0;
}