题目描述

你有一个正整数 $k$ 和一个长度为 $n$​ 的序列 $p$​，但你并不完全知道这个序列。

但你知道序列的每个数都是 $[1,k]$ 中的整数。

现在序列中有一些数的取值已经确定了，但剩下的能取 $[1,k]$ ​​中的任意数。

你喜欢逆序对，所以你希望知道这个序列最多可能有多少个逆序对。

输入格式

第一行两个整数 $n,k$​​​​ 意义如上。

接下来一行 $n$​​ 个整数，第 $i$​ 个数表示$p_i$​，每个数为 $[0,k]$​​ 中的一个整数，其中 $0$​​​ 这个数的取值还不知道。不为 $0$ 表示这个数的取值已经确定了。

输出格式

输出一个正整数表示最大的逆序对数量

6 6
5 0 1 4 0 6

7

11 9
9 0 3 0 0 4 7 1 0 2 0

44

样例解释 1

一种方案是将序列填为5 5 1 4 1 6，可以得出此时逆序对数为7且没有更多逆序对的情况

数据范围与约定

对于$100\%$的数据，保证$1\le n\le 200000,1\le k\le 100,0\le p_i\le k$

大样例

大样例下载