分数: 800 点
问题陈述
Snuke 收到了排列 P=(P_1,P_2,\cdots,P_N) of (1,\ 2,\ ...\ N) 和一个整数 K。 他对两个相邻元素进行了一些交换 P 以便满足以下条件。
- 对于每个 1 \leq i \leq N,最多有 K 指数 j 这样 1 \leq j< i 和 P_j>P_i.
在这里,他做了 最小值 达到此条件所需的交换次数。
之后,他忘记了他收到的原始排列。 给定排列 P' 交换后,找到数字,模 998244353,原始排列的排列 P 可能是。
约束
- 2 \leq N \leq 5000
- 1 \leq K \leq N-1
- 1 \leq P'_i \leq N
- P'_i \neq P'_j (i \neq j)
- 对于每个 1 \leq i \leq N,最多有 K 指数 j 这样 1 \leq j< i 和 P'_j>P'_i.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K P'_1 P'_2 \cdots P'_N
输出
打印答案。
示例输入 1
3 1 3 1 2
示例输出 1
2
P 可以是以下两种排列之一。
- P=(3,1,2):所需的最小交换次数为 0。零交换后,排列等于 P'.
- P=(3,2,1):所需的最小交换次数为 1:交换 P_2 和 P_3 结果 P=(3,1,2),满足条件并且等于 P'.
示例输入 2
4 3 4 3 2 1
示例输出 2
1
示例输入 3
5 2 4 2 1 5 3
示例输出 3
3