Optimal File System Block Reassignment

The command center uses a special secure operating system with a unique file system. In this file system, the entire disk is divided into N blocks (numbered from 1 to N). Each file occupies one or more blocks, and any block not occupied by a file is free. For maximum read speed, files should be stored in contiguous disk blocks. In addition, files are pre‐assigned a frequency rank from 1 to K (with 1 being the highest frequency). In the optimal arrangement, file 1 occupies blocks 1 through S₁, file 2 occupies blocks S₁+1 through S₁+S₂, and so on (where S_i is the number of blocks occupied by the i^th file).

However, currently the files might be scattered over the disk. To achieve the optimal ordering, we are allowed to perform block move operations. A block move operation consists of reading an occupied block from the disk into memory and writing it into an empty block. After the move the original block becomes free and the destination block becomes occupied. It is important that for any file the relative order of its blocks must remain unchanged after moves.

Your task is to compute the minimum number of block move operations required to rearrange the files to their optimal layout.

Hint: Consider the sequence formed by the file ID (ignoring free blocks) in the order of disk block positions. The problem reduces to retaining a longest non-decreasing subsequence (where file IDs are in non-decreasing order) and moving the other blocks.

Formally, if the total number of occupied blocks is T and the length of the longest non-decreasing subsequence is L, then the answer is T - L.

Note: All formulas are presented in LaTeX format. For example, the block range for file 1 is given by $1,2,\ldots,S_1$, and for file i it is $\left(\sum_{j=1}^{i-1}S_j+1\right), \ldots, \left(\sum_{j=1}^{i}S_j\right)$.

inputFormat

The first line contains two integers N and K — the number of disk blocks and the number of files, respectively.

The second line contains N integers separated by spaces. Each integer is either 0 (indicating a free block) or an integer between 1 and K (indicating the file ID that occupies that block). It is guaranteed that each file appears at least once.

outputFormat

Output a single integer — the minimum number of block move operations required to rearrange the files into the optimal layout.

sample

5 2
1 0 1 2 2

0