← 返回题目列表

AtCoder · pakencamp_2021_day2_m

M. 双端队列和反转

中文机器翻译题面 查看原题

配点 : 600 点

問題文

正整数 给出了 N 。夏尾君是一个空数列 准备好 Q 后, 重新排列的序列(1,2,\dots,N) 自由选择 P=(P_1, P_2, \dots, P_N) 并执行以下一系列操作。 N 次。

  1. P 的第一个元素 作为 x , 在Q 的开头或结尾 添加 x 。 删除
  2. P 它们的编号最大为 x 。

夏尾君是最后的 适当操作以尽量减少 Q 跌倒的次数。 可以认为是

P 的是 N! 方法有很多,但是对于所有的方法,操作后 找出 Q 的最少跌倒次数并计算总数 请打印除以 998244353 后的余数。

跌倒次数是多少?

(1,2,\dots,N) 自由选择 P'=(P'_1, P'_2, \dots, P'_N) 的跌倒次数为1 \leq i < j \leq N 整数 i,j , 指的是满足P'_i > P'_j 的事物的数量。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N

出力

答案 1 行输出。


入力例 1

4

出力例 1

20

例如, 经过P=(3,2,1,4) ,通过执行适当的操作。 Q=(1,2,3,4) 跌倒次数为 0 。

其他 如果我们对 P 进行类似计算,答案是 事实证明 20 。


入力例 2

220328

出力例 2

192799865

原案: 夏美曾严