408762: GYM103295 J The Culk's Incredible Buffet

The Culk is infamous for his humongous appetite, but his doctor told him to cut back on the Hobbit-like eating habits. It goes without saying that the Culk expressed his displeasure by "CULK SMASH"ing the doctor's office before a compromise was made. Now the Culk can eat a massive meal every day, as long as it is composed of exactly $$$K$$$ distinct course types (each labeled by an integer from $$$1$$$ to $$$K$$$, inclusive) in the order that the doctor has prescribed (increasing numerical value). Since it is a Herculean task to provide the necessary dishes to the dieting Culk, the Revengers team have outsourced the task to a revolving sushi bar.

The sushi bar outputs an ordered menu of $$$N$$$ course dishes, each of course type $$$1\dots K$$$, in a rotating cycle (assume the number of cycles is infinite for this very busy sushi bar). For example, if the menu consists of courses $$$1$$$, $$$2$$$, and $$$3$$$ in that order, the first $$$7$$$ dishes outputted by the sushi bar would be $$$1$$$, $$$2$$$, $$$3$$$, $$$1$$$, $$$2$$$, $$$3$$$, and $$$1$$$. Although the head chef is being paid a handsome amount to service the needs of the Culk, they want the Culk to wait the least amount of time between the first dish served and the last dish consumed in order to minimize the chances of him wrecking the restaurant. Each course dish takes an equal amount of time to prepare, so minimizing the number of dishes served between and including the first and last dishes the Culk consumes is equivalent. Given that the Culk eats every dish type $$$1\dots K$$$ exactly once in increasing order, what is the minimum number of dishes the Culk needs to sit through to meet his dietary requirements?

The first line of input contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq K \leq N \leq 500000$$$) representing the number of dishes on the menu and the number of course types. The second line of input contains $$$N$$$ positive integers at most $$$K$$$ that represent the dish types on the menu in order. It is guaranteed that there is at least one instance of dish $$$x$$$ being served on the menu for $$$1 \leq x \leq K$$$ (in other words, the Culk will be able to finish his full meal).

Output a single integer representing the number of dishes that will be outputted between the first and last courses, inclusive, consumed by the Culk if his time seated at the restaurant is minimized.

5 4
4 3 1 2 1

9

For the sample input, the Culk can start by consuming the 3rd dish of the 1st cycle. The 4th dish of the 1st cycle, the 2nd dish of the 2nd cycle, and the 1st dish of the 3rd cycle complete the meal for a total of $$$1 + 1 + 3 + 4 = 9$$$ dishes.