Minimum Moves for Container Reordering

A company operates N stores and sells M different products. The company’s central warehouse packages products for delivery to the stores. In packaging, each store receives the same number of each product. In other words, the warehouse prepares exactly N × M containers, and for each product labeled from 1 to M, there are exactly N containers marked with that product’s label.

The containers are initially arranged in a single row in the narrow warehouse building, and there is one empty slot at the very end of the row. To speed up deliveries, the warehouse manager plans to reorder the containers. The desired final arrangement is as follows: The first M containers (positions 1 to M) must have distinct product labels, the next M containers (positions M+1 to 2M) must also have distinct labels, and so on. Finally, the empty slot must remain at the end of the row after reordering.

The only allowed operation is to pick up a container from its current position and move it to the empty slot; the container’s old position then becomes empty. Your task is to compute the minimum number of moves required to achieve a valid reordering.

Observation: Since each store should receive exactly one container for each product, one can think of the final arrangement as partitioning the container positions into N consecutive blocks of size M, where each block must contain exactly one container of each product from 1 to M. A container that is already in a block where its label appears uniquely (i.e. no other container in that block has the same label) can be left in place. In a block, if a product appears more than once, only one occurrence can remain; the others have to be moved. Thus, if we compute, for each block, the number of unique labels present, and sum these counts over all blocks, this represents the maximum number of containers that can stay in place. Since there are a total of N × M containers to position, the minimum number of moves is given by:

[ \text{moves} = N \times M - \sum_{i=1}^{N} \left(\text{number of unique labels in block } i\right) . ]

Note that the input is guaranteed to have exactly N occurrences of every product label (overall), so a valid reordering is always possible.

inputFormat

The first line contains two integers, N and M (1 ≤ N, M ≤ 10⁵), separated by a space.

The second line contains N × M integers, representing the product labels of the containers in their current order. The containers are given in order from the first position up to the N × M-th position. (It is guaranteed that each product from 1 to M appears exactly N times.)

There is an extra empty slot at the end (which is not listed in the input) and must remain empty in the final arrangement.

outputFormat

Output a single integer: the minimum number of moves required to achieve a reordering where every block of M consecutive containers has all distinct product labels and the empty slot remains at the end.

sample

1 3
1 2 3

0