ABC 339

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

    ll N;
    cin >> N;

    vector<string> grid(N);
    rep(i, N) cin >> grid[i];
    vector dist(N, vector(N, vector(N, vll(N, INF))));

    using P = tuple<ll, ll, ll, ll>;
    queue<pair<P, ll>> que;
    {
        vector<pair<ll, ll>> v;
        rep(i, N) rep(j, N) {
            if (grid[i][j] == 'P') v.emplace_back(i, j);
        }

        que.emplace(P({v[0].first, v[0].second, v[1].first, v[1].second}), 0);

        auto [p, _] = que.front();
        auto [i, j, k, l] = p;
        dist[i][j][k][l] = 0;
    }

    auto is_stay = [&](ll i, ll j) -> bool {
        if (clamp(i, 0ll, N - 1) != i || clamp(j, 0ll, N - 1) != j) return true;
        return grid[i][j] == '#';
    };

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    while (que.size()) {
        auto [p, cost] = que.front();
        que.pop();

        auto [pi, pj, qi, qj] = p;

        if (dist[pi][pj][qi][qj] < cost) continue;

        rep(d, 4) {
            ll npi = pi + di[d], npj = pj + dj[d];
            if (is_stay(npi, npj)) {
                npi = pi, npj = pj;
            }
            ll nqi = qi + di[d], nqj = qj + dj[d];
            if (is_stay(nqi, nqj)) {
                nqi = qi, nqj = qj;
            }

            if (cost + 1 < dist[npi][npj][nqi][nqj]) {
                dist[npi][npj][nqi][nqj] = cost + 1;
                que.emplace(P({npi, npj, nqi, nqj}), cost + 1);
            }
        }
    }

    ll ans = INF;

    rep(i, N) rep(j, N) {
        chmin(ans, dist[i][j][i][j]);
    }

    if (ans == INF) ans = -1;
    cout << ans << endl;
}

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

    ll N, D;
    cin >> N >> D;
    vll A(N);
    rep(i, N) cin >> A[i];

    auto op = [](ll a, ll b) -> ll {
        return max(a, b);
    };

    auto e = []() -> ll {
        return 0;
    };

    ll M = 5e5;
    segtree<ll, op, e> seg(M + 2);

    for (ll x : A) {
        ll l = max(0ll, x - D);
        ll r = min(M, x + D) + 1;

        ll mx = seg.prod(l, r);
        seg.set(x, mx + 1);
    }

    cout << seg.all_prod() << endl;
}