ABC 336

void solve() {
    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    A.push_back(0);
    A.insert(A.begin(), 0);

    N += 2;
    vll dl(N, 0), dr(N, 0);
    rep2(i, 1, N) {
        dl[i] = min(dl[i - 1] + 1, A[i]);
    }

    rep(i, N - 1) {
        int k = N - 1 - i;
        dr[k - 1] = min(dr[k] + 1, A[k - 1]);
    }

    ll ans = 0;
    rep(i, N) {
        chmax(ans, min(dr[i], dl[i]));
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    vint v;
    {
        ll tmp = N;
        while (tmp) {
            v.push_back(tmp % 10);
            tmp /= 10;
        }
        reverse(all(v));
    }

    // 桁和の最大値 9*14=126
    int max_sum = 9 * 14;
    int MOD = max_sum + 1;

    // dp[is_less][sum of digit][m][mod]
    vector dp(2, vector(max_sum + 1, vector(MOD, vll(MOD))));
    rep(i, MOD) dp[0][0][i][0] = 1;
    int L = v.size();

    rep(i, L) {
        int t = v[i];
        vector dpn(2, vector(max_sum + 1, vector(MOD, vll(MOD))));

        rep(d, 10) rep(is_less, 2) rep(sum, max_sum + 1) rep2(div, 1, MOD) rep(mod, MOD) {
            if (!is_less && d > t) continue;
            if (dp[is_less][sum][div][mod] == 0) continue;

            int is_less_n = is_less || d < t;
            int sum_n = sum + d;
            int rem_n = (mod * 10 + d) % div;

            dpn[is_less_n][sum_n][div][rem_n] += dp[is_less][sum][div][mod];
        }

        swap(dp, dpn);
    }

    ll ans = 0;
    rep2(sum, 1, max_sum + 1) rep(is_less, 2) {
        ans += dp[is_less][sum][sum][0];
    }
    cout << ans << endl;
}