P9959 [USACO19JAN] Sleepy Cow Sorting B

Farmer John is trying to line up his $N$ cows ($1\le N\le 100$), conveniently numbered $1\ldots N$, before they head to the pasture to eat breakfast. Currently, the cows are standing in a line in the order $p_1,p_2,p_3,\ldots,p_N$, and Farmer John is standing in front of cow $p_1$. He wants to rearrange the cows so that their order becomes $1,2,3,\ldots,N$, with cow $1$ next to Farmer John. Today the cows are a bit sleepy, so at any moment only the cow directly facing Farmer John will pay attention to his commands. In one move, he can command this cow to move back along the line by $k$ steps, where $k$ can be any integer in the range $1\ldots N-1$. The $k$ cows she passes will move forward to make space, allowing her to be inserted into the position after those $k$ cows. For example, suppose $N=4$, and the cows initially are in the following order: > FJ: $4, 3, 2, 1$ The only cow paying attention to FJ is cow $4$. After he commands her to move back by $2$ steps, the order becomes: > FJ: $3, 2, 4, 1$ Now the only cow paying attention to FJ is cow $3$, so on the second move he can command cow $3$, and so on until the cows are sorted. Farmer John is eager to finish sorting so he can go back to his farmhouse and eat his own breakfast. Please help him find the minimum number of moves required to sort the cows.

The first line contains $N$. The second line contains $N$ space-separated integers $p_1,p_2,p_3,\ldots,p_N$, representing the cows' initial order.

Output one integer: the minimum number of moves needed for Farmer John to sort these $N$ cows using an optimal strategy.

Translated by ChatGPT 5