역전쌍

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

요약

길이 n의 수열에서 0으로 표시된 빈칸을 1부터 k까지의 값으로 채워 역전 쌍의 수를 최대로 만드는 문제입니다.

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

문제

길이가 $n$ 인 정수 수열이 주어집니다. 각 원소는 $1$ 이상 $k$ 이하입니다. 일부 정수는 값을 모르며 $0$ 으로 표시되어 있습니다.

역전쌍은 위치 $i$ 와 $j$ 의 쌍으로, $i<j$ 이고 $a_i > a_j$ 를 만족합니다. 빈칸을 모두 $1$ 이상 $k$ 이하의 정수로 채울 때, 가능한 역전쌍의 최대 개수를 구하세요.

입력

첫 줄에 정수 $n$ ( $1 \le n \le 200{,}000$ )과 $k$ ( $1 \le k \le 100$ )가 공백으로 구분되어 주어집니다. $n$ 은 수열의 길이이고, $k$ 는 원소의 최댓값입니다. 이어지는 $n$ 개의 줄에는 수열의 원소 $x$ ( $0 \le x \le k$ )가 순서대로 한 줄에 하나씩 주어집니다. $0$ 은 빈칸을 뜻합니다.

출력

가능한 역전쌍의 최대 개수를 정수 하나로 출력하세요.

힌트

첫 번째 예에서 $0$ 을 다음과 같이 채우면

9 8 4 3 2 1

수열의 모든 쌍이 역전쌍이 되어 총 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
```