시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 2 2 66.667%

문제

Consider a sequence of n integers, all of them between 1 and k (inclusive). Some of the integers are missing, and are replaced with 0s.

An inversion is a pair of values ai and aj in the sequence, where i<j, but ai>aj. What’s the maximum number of inversions possible if the missing integers are all between 1 and k inclusive?

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs.

Each test case will start with a line with two space-separated integers n (1 ≤ n ≤ 200,000) and k (1 ≤ k ≤ 100), where n is the length of the sequence and k is the maximum value of elements of the sequence.

Each of the next n lines will contain a single integer x (0 ≤ x ≤ k). This is the sequence, in order, with 0s representing the missing values.

출력

Output a single integer, which is the maximum number of inversions possible.

예제 입력 1

6 9
0
8
4
3
0
0

예제 출력 1

15

예제 입력 2

10 9
5
2
9
0
7
4
8
7
0
0

예제 출력 2

28

예제 입력 3

10 9
7
4
0
0
8
5
0
0
3
1

예제 출력 3

36

힌트

In the first example, if you replace the 0s like this:

9 8 4 3 2 1

Then every pair of numbers in the sequence is an inversion, for a total of 15.