I - Increasing Subsequence

思路：
直接往期望上面靠。设为前次取第个数字，前前次取第个数字的期望轮数。因为要满足后面的比前面的下标要大，如果从前往后取的话，每次都要找后面的数字中比当前两个数字都大的数字，时间复杂度为，是接受不了的。既然要求每次都要取后面的数字，那么不如从后面开始转移，转移到前面，就不用再往后找了。

为了保证正确的转移，我们不能将的两维都直接从数组里面取，不然两个都一直变大变小，不太好符合题目要求。尝试固定其中一维为具体的数字，从大到小进行遍历，另一维就能在数组里遍历了。

设为前次取的数字大小为，前前次取的数字大小为，取到此状态一直到结束时的期望轮数。设为第一维是时的期望和，为当前比大的数字的个数。如果当前的比取的数字要大的话，就是一个合法的情况，把此状态下的期望轮数加入期望和中，并让；如果比要小的话，因为第一维为，并且第二维数字比大，下标比大的情况已经都更新过了，所以就可以用当前的来更新。

#include <bits/stdc++.h>

using namespace std;

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 5e3 + 7;

ll powmod(ll a, ll b) {
    a %= mod;
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void add(ll &a, ll b) {
    a += b;
    a %= mod;
}

ll dp[N][N], inv[N], a[N];

void solve() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
    }
    for (int i = n; i >= 0; --i) {
        int cnt = 0;
        ll sum = 0;
        for (int j = n; j >= 0; --j) {
            if (a[j] < i) {
                add(dp[a[j]][i], 1 + sum * inv[cnt]);
            }
            if (a[j] > i) {
                add(sum, dp[i][a[j]]);
                cnt++;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        add(ans, dp[0][i]);
    }
    ans = ans * inv[n] % mod;
    printf("%lld\n", ans);
}

int main() {
    for (int i = 1; i < N; ++i) {
        inv[i] = powmod(i, mod - 2);
    }
    int t = 1;
    while (t--) solve();
    return 0;
}