配点 : $600$ 点

問題文

$A_1=0$ かつ $A_N>0$ であるような、$N$ 個の非負整数の組 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

高橋君は $N$ 個のカウンターを持っており、最初、全てのカウンターの値は $0$ です。 高橋君は、全ての $1\leq i\leq N$ について $i$ 番目のカウンターの値が $A_i$ 以上となるまで次の操作を繰り返します。

$N$ 個のカウンターの中から $1$ つを等確率に選び、その値を $0$ にする。（選択は毎回独立に行う。） 選んだカウンター 以外 のカウンターの値を $1$ 増加させる。

高橋君の操作回数の期待値を $\mathrm{mod}$ $998244353$ で出力してください（注記参照）。

注記

求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P\pmod{998244353}$ かつ $0 \leq R \lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $2\leq N\leq 2\times 10^5$
• $0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}$
• $A_N>0$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

高橋君の操作回数の期待値を $\mathrm{mod}$ $998244353$ で出力せよ。

2
0 2

6

$i$ 番目のカウンターの値を $C_i$ で表します。

高橋君の操作が終了するまでの一連の流れの例は次の通りです。

• $1$ 番目のカウンターの値を $0$ にした後、それ以外のカウンターの値を $1$ 増加させる。 $(C_1,C_2)=(0,1)$ となる。
• $2$ 番目のカウンターの値を $0$ にした後、それ以外のカウンターの値を $1$ 増加させる。 $(C_1,C_2)=(1,0)$ となる。
• $1$ 番目のカウンターの値を $0$ にした後、それ以外のカウンターの値を $1$ 増加させる。 $(C_1,C_2)=(0,1)$ となる。
• $1$ 番目のカウンターの値を $0$ にした後、それ以外のカウンターの値を $1$ 増加させる。 $(C_1,C_2)=(0,2)$ となる。

この場合の操作回数は $4$ となります。

$1,2,3,4,5,\ldots$ 回で操作が終了する確率はそれぞれ $0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots$ であり、 期待値は $2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6$ となります。 よって、 $6$ を出力します。

5
0 1 3 10 1000000000000000000

874839568