16418번 - Inversions 다국어

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 a_i and a_j in the sequence, where i<j, but a_i>a_j. 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.