Description

The summer vacation has arrived. Keke and friends are on a beach holiday. Not far from the shore lies a small island called Happy Island. The whole island is a big amusement park with many fun puzzle games. By chance, the island is running an event: “Solve puzzles to win free tickets.” If you solve the puzzle, Keke and friends can play on Happy Island for two days for free.

The puzzle is: given a sequence of positive integers, all chosen from within a certain range, whoever can find the number of “inversion pairs” in the sequence the fastest wins the prize.

Of course, the organizer will not make it that easy. The sequence has been processed: some numbers are deliberately hidden and replaced by −1. To win the prize, you must find the minimum possible number of inversion pairs that the processed sequence can have. Keke really wants that free chance to play. Can you help?

Note: An “inversion pair” means that if there are two numbers A and B, A is to the left of B and A > B, then (A, B) is an inversion pair. For example: in 4 2 1 3 3, there are 5 inversion pairs: (4, 2), (4, 1), (4, 3), (4, 3), (2, 1).

Suppose the sequence has 5 positive integers, and each number N is between $1$ and $4$. After replacing some numbers by “−1”, e.g., 4 2 −1 −1 3, the original sequence could be 4 2 1 3 3, or 4 2 4 4 3, or something else. Your task is to infer, based on the known numbers, the minimum possible number of inversion pairs in the sequence.

Input Format

The first line contains two positive integers $N$ and $K$.

The second line contains $N$ integers, each either $-1$ or a number in $1$ to $K$. ($N \le 10000$, $K \le 100$.)

Output Format

A single positive integer: the minimum number of inversion pairs in the sequence.

5 4
4 2 -1 -1 3

4

Hint

• For 100% of the testdata, $N \le 10000$, $K \le 100$.
• For 60% of the testdata, $N \le 100$.
• For 40% of the testdata, $-1$ appears no more than twice.

Translated by ChatGPT 5