以下、 \(A\) は広義単調増加 \((A_1\leq A_2\leq\cdots\leq A_N)\)であるとします。 (今回は制約で保証されていますが、そうでなくてもソートすれば良いです。)

1. 状態をまとめ、遷移を整理する

カウンターの値の組 \((C_1,C_2,\ldots,C_N)\) に対して、その組の 状態 を \(\max(A_1-C_1,A_2-C_2,\ldots,A_N-C_N)\) で定めます。 初期状態は \(A_N(>0)\) であり、 状態が \(0\) 以下のとき、かつその時に限り、操作は終了します。 \(\max\) の各項は\(1\) 回の操作で高々 \(1\) しか減少しないため、状態も高々 \(1\) しか減少せず、また、つねに \(C_i\geq 0\) が成り立つため、状態が \(0\) 以上 \(A_N\) 以下の時のみ考えれば良いです。

ここで、状態の値が定まっている時、具体的なカウンターの値の組によらず、そこから \(1\) 回操作を行った時に、それぞれのカウンターを選んだ時の遷移先の状態が定まります。実際、現在の状態を \(k\) \((1\leq k\leq A_N)\) とすると、そこからは操作によって次のように遷移します。

操作前のカウンターの値を \(C_1,C_2,\ldots,C_N\) とすると、 \(i\) 番目のカウンターが選ばれた時、 操作後の状態は、 \(\max\left( A_i, \displaystyle\max_{j\neq i}(A_j-(C_j+1))\right)\) となることに注意します。 また、ある \(1\leq r\leq N-1\) が存在して、 \(A_r<k\leq A_{r+1}\) が成り立つため、このような \(r\) を取ります。

• 操作で選んだカウンターが \(i\) 番目 \((1\leq i\leq r)\) であったとき

\(A_i\leq k-1\) かつそれ以外のカウンターの値は増加するため、 \(A_j-(C_j+1)\leq k-1\)となるため、状態は \(k-1\)以下となります。 一度の操作で高々 \(1\) しか減少しないため、操作後の状態は \(k-1\) となります。

• 操作で選んだカウンターが \(i\) 番目 \((r+1\leq i\leq N)\) であったとき

状態は \(A_i\) 以上であり、それ以外の項については \(A_j-(C_j+1)\leq k-1<A_i\)となるため、状態は \(A_i\)となります。

2. 期待値についての漸化式を立てる

遷移が分かれば、それぞれの状態から（操作を終えるまで）の操作回数の期待値を定義して、その間の関係式を得る事ができます。状態 \(k\) \((0\leq k\leq A_N)\) からの操作回数の期待値を \(x_k\) とすると、先の遷移から、\(1\leq k\leq A_N\)について、

\[ x_k=\frac{1}{N}\left(rx_{k-1}+\displaystyle\sum_{i=r+1}^N x_{A_i} \right)+1 \]

が成り立ち、これを整理すると、

\[ x_{k-1}=\frac{1}{r}\left(N(x_k-1)-\displaystyle\sum_{i=r+1}^N x_{A_i} \right) \]

となります。ここで、 \(r+1\leq i\leq N\) について、\(k-1<A_i\) であることに注意します。
しかし、初期条件は \(x_0=0\) であり、求めたいものは \(x_{A_N}\) であるため、 \(x_{k-1}\) が それより大きい添字から定まっている現在の漸化式は都合が悪いです。

そこで、 \(y_k=x_{A_N}-x_k\) として置き直します。すると、初期条件は \(y_{A_N}=0\), 求めたいものは \(x_{A_N}=y_0\) となり、漸化式は先の式の両辺を \(x_{A_N}\) から引いて、

\[ x_{A_N}-x_{k-1}=x_{A_N}-\frac{1}{r}\left(N(x_k-1)-\displaystyle\sum_{i=r+1}^N x_{A_i} \right) \]

となり、これを整理して、

\[ y_{k-1}=\frac{1}{r}\left(N(y_k+1)-\displaystyle\sum_{i=r+1}^N y_{A_i} \right) \]

となります。 よって、 \(y_{A_N}=0\)から始めて、この漸化式を用いて順に \(y_{A_N-1}\), \(y_{A_N-2}\), \(\ldots\), \(y_0\) を求める事ができ、 \(O(A_N\log P)\) で答えを求める事ができます。 ここで、\(P\) は 法とする素数で今回の場合は \(P=998244353\) です。 しかし、今回の制約では \(A_N\leq 10^{18}\) ですから、これでは不十分です。

3.高速化

\(y_{A_N}=0\) から始めて、\(y_{A_{N-1}}\), \(y_{A_{N-2}}\), \(\ldots\), \(y_{A_1}(=y_0)\) を順に求めることを考えます。
\(s_r\) \((1\leq r\leq N-1)\) を \(s_r=\displaystyle\sum_{i=r+1}^N y_{A_i} \) で 定めると、\(A_r<k\leq A_{r+1}\) をみたす \(k\)について、

\[ y_{k-1}=\frac{1}{r}\left(N(y_k+1)-s_r\right) \]

が成り立ち、これを整理すると、

\[ y_{k-1}+\frac{N-s_r}{N-r}=\frac{N}{r}\left(y_k+\frac{N-s_r}{N-r}\right) \]

となります。これが \(A_r<k\leq A_{r+1}\) をみたすすべての \(k\) について成り立つことから、

\[ y_{A_r}+\frac{N-s_r}{N-r}=\left(\frac{N}{r} \right)^{A_{r+1}-A_r}\left(y_{A_{r+1}}+\frac{N-s_r}{N-r}\right) \]

であり、整理して、

\[ y_{A_r}=\left(\frac{N}{r} \right)^{A_{r+1}-A_r}\left(y_{A_{r+1}}+\frac{N-s_r}{N-r}\right)-\frac{N-s_r}{N-r} \]

を得ます。 \(s_r\) は、\(s_{N-1}=0\), \(s_{r}=s_{r+1}+y_{A_{r+1}}\) \((1\leq r\leq N-2)\) として求まります。

よって、これらを用いて \(y_{A_{N-1}}\), \(y_{A_{N-2}}\), \(\ldots\), \(y_{A_1}(=y_0)\) を順に求める事ができ、求めたいものは \(y_0\) であった事から、\(O(N(\log A_N+\log P))\) で計算する事ができ、十分高速にこの問題を解く事ができました。

なお、この途中で逆元をとる対象は \(r,N-r\) \((1\leq r\leq N-1)\) のみであるため、\(\bmod {P}\) で逆元を取ることが問題なく行えます。

c++ による実装例 :

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main(void) {
    int n;
    cin>>n;
    vector<long long>a(n);
    vector<mint> y(n);
    mint s,x,z;
    for(int i=0;i<n;i++)cin>>a[i];

    y[n-1]=0;
    s=0;
    for(int i=n-1;i>=1;i--){
        x=((mint)n/i).pow(a[i]-a[i-1]);
        z=(n-s)/(n-i);
        y[i-1]=(y[i]+z)*x-z;
        s += y[i-1];
    }
    
    cout<< y[0].val() <<endl;
    return 0;
}