Here, we assume that \(A\) is weakly monotonically increasing \((A_1\leq A_2\leq\cdots\leq A_N)\). (It is guaranteed in this problem, but we can sort it otherwise.)

1. Group the states to reorganize the transition

For a tuple of values of counters \((C_1,C_2,\ldots,C_N)\), let us define the state of the tuple by \(\max(A_1-C_1,A_2-C_2,\ldots,A_N-C_N)\). The initial state is \(A_N(>0)\), and the operations end if and only if the state is less than or equal to \(0\). Since each term of \(\max\) decreases by at most \(1\) in one operation, so does the state, and since we always have \(C_i\geq 0\), we need to consider only when the state is between \(0\) and \(A_N\), inclusive.

Here, when we know the value of the state, regardless of the actual tuple of the values of counters, we can determine the destination of the transition when each counter is selected. Actually, when the current state is \(k\) \((1\leq k\leq A_N)\), it transitions as follows:

Note that, if the values of counters before an operation is \(C_1,C_2,\ldots,C_N\), when the \(i\)-th counter was chosen, the state becomes \(\max\left( A_i, \displaystyle\max_{j\neq i}(A_j-(C_j+1))\right)\) after the operation. Also, there exists \(1\leq r\leq N-1\) such that \(A_r<k\leq A_{r+1}\), so take this \(r\).

• If the \(i\)-th \((1\leq i\leq r)\) counter was chosen

\(A_i\leq k-1\), and the values of the other counters increase, so \(A_j-(C_j+1)\leq k-1\), making the state less than \(k\). Since it decreases by at most \(1\) by an operation, the state becomes \(k-1\) after the operation.

• If the \(i\)-th \((r+1\leq i\leq N)\) counter was chosen

The state becomes greater than or equal to \(A_i\), and for the other terms, \(A_j-(C_j+1)\leq k-1<A_i\), so the state becomes \(A_i\).

2. Finding the recurrence relation for the expected value

Once the transitions are known, we can define the expected value of the time the operation is performed from each state (to the end of the operations) and obtain the relations between them. Let us denote by \(x_k\) the expected value of the operations, then by the transitions we mentioned before, we have

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

for all \(1\leq k\leq A_N\); equivalently, we have

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

Here, note that \(k-1<A_i\) for all \(r+1\leq i\leq N\).
However, the initial condition is \(x_0=0\), and what we want is \(x_{A_N}\), so the current recurrence relation where \(x_{k-1}\) is defined by those with larger indices are ill-formed.

Instead, let us rewrite with \(y_k=x_{A_N}-x_k\). Then the initial condition is \(y_{A_N}=0\) and the desired value is \(x_{A_N}=y_0\). By subtracting from \(x_{A_N}\) the both hand sides of the equation above, the recurrence relation becomes

\[ 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) \]

or equivalently

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

Therefore, starting from \(y_{A_N}=0\), we can use this recurrence relation to find \(y_{A_N-1}\), \(y_{A_N-2}\), \(\ldots\), and \(y_0\) in this order, so the problem is found in a total of \(O(A_N\log P)\) time. Here, \(P\) is the prime for the modulus; this time, \(P=998244353\). However, in this constraints, \(A_N\leq 10^{18}\), so this is not enough.

3. Optimization

Consider starting from \(y_{A_N}=0\) and finding \(y_{A_{N-1}}\), \(y_{A_{N-2}}\), \(\ldots\), and \(y_{A_1}(=y_0)\) in this order.
Defining \(s_r\) \((1\leq r\leq N-1)\) by \(s_r=\displaystyle\sum_{i=r+1}^N y_{A_i} \), for all \(k\) such that \(A_r<k\leq A_{r+1}\), we have

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

or equivalently

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

Since this holds for all \(k\) such that \(A_r<k\leq A_{r+1}\), we have

\[ 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), \]

thus we obtain

\[ 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\) is obtained by \(s_{N-1}=0\) and \(s_{r}=s_{r+1}+y_{A_{r+1}}\) \((1\leq r\leq N-2)\).

Therefore, we can use these values to find \(y_{A_{N-1}}\), \(y_{A_{N-2}}\), \(\ldots\), \(y_{A_1}(=y_0)\) in this order. What we want, \(y_0\), can be computed in a total of \(O(N(\log A_N+\log P))\) time, so the problem has been solved fast enough.

The computation requires inverses only for \(r\) and \(N-r\) \((1\leq r\leq N-1)\), which we can find without issues.

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;
}