Comet OJ

C1806 [AHOI2008]逆序对

内存限制：256 MB 时间限制：1000 ms

题目描述

小可可和小卡卡想到 Y 岛上旅游，但是他们不知道 Y 岛有多远。好在，他们找到一本古老的书，上面是这样说的：

下面是 $N$ 个正整数，每个都在 $1\sim K$ 之间。如果有两个数 $A$ 和 $B$，$A$ 在 $B$ 左边且 $A$ 大于 $B$，我们就称这两个数为一个“逆序对”。你数一数下面的数字里有多少个逆序对，你就知道 Y 岛离这里的距离是多少千米了。

比如说，4 2 1 3 3 里面包含了 $5$ 个逆序对：(4, 2), (4, 1), (4, 3), (4, 3), (2, 1)。 可惜的是，由于年代久远，这些数字里有一部分已经模糊不清了，为了方便记录，小可可用“-1”表示它们。比如说，4 2 -1 -1 3 可能原来是 4 2 1 3 3，也可能是 4 2 4 4 3，也可能是别的样子。 小可可希望知道，根据他们看清楚的这部分数字，能不能推断出这些数字里最少能有多少个逆序对。

输入格式

第一行两个正整数 $N$ 和 $K$。第二行 $N$ 个整数，每个都是 $-1$ 或是一个在 $1\sim K$ 之间的数。

输出

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

样例

样例输入 1

5 4
4 2 -1 -1 3

样例输出 1

4

提示

数据范围：

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

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

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