AT_pakencamp_2021_day2_m Deque and Inversions

给定一个正整数 $N$。Natsubi 君开始时有一个空的数列 $Q$。他要从一个由 $(1, 2, \dots, N)$ 生成的任意排列数列 $P = (P_1, P_2, \dots, P_N)$ 中选择一个，然后进行如下步骤，重复 $N$ 次： 1. 从 $P$ 的开头取出第一个元素 $x$，将 $x$ 添加到 $Q$ 的开头或末尾。 2. 从 $P$ 中移除元素 $x$。 Natsubi 君的目标是使得最终数列 $Q$ 的逆序对数尽可能少。在所有可能的数列 $P$（共有 $N!$ 种）中，他需要计算操作后 $Q$ 的逆序对数最小值之和。最后，求出这个和对 $998244353$ 取余的结果。 逆序对数是什么？对于一个由 $(1, 2, \dots, N)$ 重新排列得到的数列 $P' = (P'_1, P'_2, \dots, P'_N)$，其逆序对数是满足 $1 \leq i < j \leq N$ 且 $P'_i > P'_j$ 的整数对 $(i, j)$ 的数量。

输入包含一个整数 $N$。

输出一个整数，表示所求值。

- $1 \leq N \leq 3 \times 10^5$ ### 样例解释 1 例如，$P = (3, 2, 1, 4)$ 时，通过适当操作可以将 $Q$ 变为 $(1, 2, 3, 4)$，这样逆序对数为 $0$。同样计算其他排列后的结果，求得答案为 $20$。 **本翻译由 AI 自动生成**