1258: #552. 「LibreOJ Round #8」MIN&MAX I

对于一个 $n$ 阶排列 $p$，我们建立一张无向简单图 $G(p)$，有 $n$ 个节点，标号从 $1$ 到 $n$，每个点向左右两侧最近的比它大的点以及比它小的点连边。
形式化地，在 $G(p)$ 中，$\forall u<v$，边 $(u,v)$ 存在当且仅当以下四个条件至少一个成立：

• pu<pvp_u<p_vp​u​​<p​v​​，且不存在 $u<i<v$ 满足 pu<pip_u<p_ip​u​​<p​i​​；
• pu>pvp_u>p_vp​u​​>p​v​​，且不存在 $u<i<v$ 满足 pu>pip_u>p_ip​u​​>p​i​​；
• pu<pvp_u<p_vp​u​​<p​v​​，且不存在 $u<i<v$ 满足 pi<pvp_i<p_vp​i​​<p​v​​；
• pu>pvp_u>p_vp​u​​>p​v​​，且不存在 $u<i<v$ 满足 pi>pvp_i>p_vp​i​​>p​v​​。

现在在所有的 $n$ 阶排列中随机选择一个排列 $p$，请求出 $G(p)$ 中三元简单环的期望个数，答案对 $998244353$ 取模。

For an $n$-order permutation $p$, we set up an undirected simple graph $G(p)$ with $n$ vertices numbered from $1$ to $n$. We create an edge between each vertice $i$ and the nearest vertices in each side which correspond a greater (or less) $p$ value than pip_ip​i​​.
Formally,in this graph, $\forall u<v$, the edge $(u,v)$ exists iff at least one of the following four conditions hold:

• pu<pvp_u<p_vp​u​​<p​v​​, and no $u<i<v$ exists such that pu<pip_u<p_ip​u​​<p​i​​;
• pu>pvp_u>p_vp​u​​>p​v​​, and no $u<i<v$ exists such that pu>pip_u>p_ip​u​​>p​i​​;
• pu<pvp_u<p_vp​u​​<p​v​​, and no $u<i<v$ exists such that pi<pvp_i<p_vp​i​​<p​v​​;
• pu>pvp_u>p_vp​u​​>p​v​​, and no $u<i<v$ exists such that pi>pvp_i>p_vp​i​​>p​v​​.

Now we randomly choose a permutation $p$ from all $n$-order permutations. Your task is to calculate the expected number of the $3$-cycles in $G(p)$. You only need to output the answer modulo $998244353$.