链接

P4280 [AHOI2008] 逆序对

题目背景

暑假到了，小可可和伙伴们来到海边度假，距离海滩不远的地方有个小岛，叫做欢乐岛，整个岛是一个大游乐园，里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动，只要猜出来迷题，那么小可可和他的朋友就能在欢乐岛上免费游玩两天。

题目描述

迷题是这样的：给出一串全部是正整数的数字，这些正整数都在一个范围内选取，谁能最快求出这串数字中“逆序对”的个数，那么大奖就是他的啦！

当然、主办方不可能就这么简单的让迷题被解开，数字串都是被处理过的，一部分数字被故意隐藏起来，这些数字均用-1来代替，想要获得大奖就必须求出被处理的数字串中最少能有多少个逆序对。小可可很想获得免费游玩游乐园的机会，你能帮助他吗？

假设这串数字由 $5$ 个正整数组成，其中任一数字 $N$ 均在 $1～4$ 之间，数字串中一部分数字被-1替代后，如：4 2 -1 -1 3，那么这串数字，可能是4 2 1 3 3，也可能是4 2 4 4 3，也可能是别的样子。你要做的就是根据已知的数字，推断出这串数字里最少能有多少个逆序对。

输入格式

第一行两个正整数 $N$ 和 $K$。

第二行 $N$ 个整数，每个都是-1或是一个在 $1$ 到 $K$ 之间的数 $(N<=10000，K<=100)$。

输出格式

一个正整数，即这些数字里最少的逆序对个数。

样例 #1

样例输入 #1

5 4
4 2 -1 -1 3

样例输出 #1

4

约束

$40\%$ 的数据中，-1出现不超过两次。

$60\%$的数据中，$N<=100$。

$100\%$ 的数据中，$N<=10000$，$K<=100$。

提示

“逆序对”就是如果有两个数 $A$ 和 $B$，$A$ 在 $B$ 左边且 $A$ 大于 $B$，我们就称这两个数为一个“逆序对”，例如：4 2 1 3 3里面包含了 $5$ 个逆序对：$(4, 2)、(4, 1)、(4, 3)、(4, 3)、(2, 1)$。