逆序数平方和

题目描述

给定长度为 $N$ 的序列 $A = (A_1,\ldots,A_N)$。$A$ 的每个元素要么是 $-1$,要么是 $1$ 到 $N$ 之间的整数,并且 $1$ 到 $N$ 的每个整数在 $A$ 中至多出现一次。

当且仅当满足 $A_i \neq -1 \Rightarrow P_i = A_i$ 时,$(1,\ldots,N)$ 的排列 $P=(P_1,\ldots,P_N)$ 被称为好排列。求所有好排列的逆序数的平方和,并对 $998244353$ 取模。

排列 $P$ 的逆序数是指满足 $1\leq i \lt j \leq N$ 且 $P_i \gt P_j$ 的整数对 $(i,j)$ 的个数。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $\ldots$ $A_N$

输出格式

输出答案。

样例

4
3 -1 2 -1

29

共有两个好排列:$P=(3,1,2,4)$ 和 $P=(3,4,2,1)$,它们的逆序数分别为 $2$ 和 $5$。

因此答案为 $2^2 + 5^2 = 29$。

10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

952235647

15
-1 -1 10 -1 -1 -1 2 -1 -1 3 -1 -1 -1 -1 1

460544744

数据范围

• $1\leq N\leq 3000$
• $A_i = -1$ 或 $1\leq A_i \leq N$
• $1$ 到 $N$ 的每个整数在 $A$ 中至多出现一次
• 所有输入值均为整数