Inversions

시간 제한2초메모리 제한512 MB

요약

1부터 k 사이의 값과 0으로 표시된 빈 자리로 이루어진 길이 n의 수열에서, 0을 1부터 k 사이 값으로 채워 역전 쌍의 개수를 최대로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 누적 합, 그리디
정답자: 아직 제출이 없습니다

문제

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.

힌트

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.

예제3

예제 1
입력
```
6 9
0
8
4
3
0
0
```
예상 출력
```
15
```
예제 2
입력
```
10 9
5
2
9
0
7
4
8
7
0
0
```
예상 출력
```
28
```
예제 3
입력
```
10 9
7
4
0
0
8
5
0
0
3
1
```
예상 출력
```
36
```