トヨタシステムズプログラミングコンテスト2025（AtCoder Beginner Contest 431）F,G 問題メモ

from bisect import bisect_left
from typing import Counter


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, d, aaa):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def nhr(n, r):
        return facts[n + r - 1] * finvs[r] % MOD * finvs[n - 1] % MOD

    cnt = Counter(aaa)
    aaa.sort()
    total = 0  # 着目中の a より小さい値の個数
    ans = 1
    for a, c in sorted(cnt.items()):
        lo = bisect_left(aaa, a - d)  # a-d より小さい値の個数
        ok = total - lo + 1  # この数字の前には置ける。あと末尾
        ans *= nhr(ok, c)
        ans %= MOD
        total += c
    return ans


n, d = list(map(int, input().split()))
aaa = list(map(int, input().split()))
ans = solve(n, d, aaa)
print(ans)

from bisect import bisect_left
from itertools import accumulate

from sortedcontainers import SortedSet
from atcoder.fenwicktree import FenwickTree


def solve(n, q, aaa, kkk):
    def prepare(n, aaa):
        fwt = FenwickTree(n + 1)
        los = [0] * n  # 自分より右にあり自分より小さい値の個数（合計が転倒数）
        for i in range(n - 1, -1, -1):
            a = aaa[i]
            los[i] = fwt._sum(a)
            fwt.add(a, 1)
        return los

    fwd_los = prepare(n, aaa)
    bbb = [n + 1 - a for a in aaa]
    rev_los = prepare(n, bbb)

    fwd_acc = [0] + list(accumulate(fwd_los))
    rev_acc = [0] + list(accumulate(rev_los))

    fwd_total = fwd_acc[-1]
    rev_total = rev_acc[-1]
    all_total = n * (n - 1) // 2
    non_change = all_total - fwd_total - rev_total
    # print(f'{fwd_total=} {rev_total=} {non_change=}')
    # print(f'{fwd_acc=}')
    # print(f'{rev_acc=}')

    idx = [-1] * (n + 1)
    same_l, same_r = -1, -1
    for i, a in enumerate(aaa):
        if idx[a] != -1:
            same_l = idx[a] + 1
            same_r = i + 1
            break
        idx[a] = i

    query_memo = [[] for _ in range(n)]
    buf = [None] * q
    for qi, k in enumerate(kkk):
        if k <= fwd_total:
            # print(f'{qi=} {k=}')
            l = bisect_left(fwd_acc, k) - 1
            order_in_l = k - fwd_acc[l] - 1
            query_memo[l].append((0, qi, l, order_in_l))
        elif k <= fwd_total + non_change:
            buf[qi] = f'{same_l} {same_r}'
        else:
            # print(f'{qi=} {k=} {all_total-k+1=}')
            k = all_total - k + 1
            l = bisect_left(rev_acc, k) - 1
            order_in_l = k - rev_acc[l] - 1
            query_memo[l].append((1, qi, l, order_in_l))

    # print(f'{query_memo=}')

    fwd_ss = SortedSet()
    rev_ss = SortedSet()
    for i in range(n - 1, -1, -1):
        for op, qi, l, order_in_l in query_memo[i]:
            if op == 0:
                _, r = fwd_ss[order_in_l]
                buf[qi] = f'{l + 1} {-r + 1}'
            else:
                _, r = rev_ss[order_in_l]
                buf[qi] = f'{l + 1} {-r + 1}'
        a = aaa[i]
        fwd_ss.add((a, -i))
        rev_ss.add((-a, -i))

    return buf


n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
kkk = [int(input()) for _ in range(q)]
ans = solve(n, q, aaa, kkk)
print('\n'.join(ans))