P5541 [USACO19FEB] Sleepy Cow Herding S

Farmer John’s $N$ cows always get lost and wander far away on the farm. He needs your help to herd them back together. The farm’s pasture is basically a long narrow region—we can think of it as a number line, and cows can stand at any integer position on this line. These $N$ cows are currently at distinct integer positions. Farmer John wants to move them so that they occupy $N$ consecutive positions (for example, positions $6$, $7$, $8$). Unfortunately, the cows are very sleepy right now, so it is not easy for Farmer John to get them to focus and follow moving orders. At any moment, he can only move a cow that is at an “endpoint” (the cow with the smallest or largest position among all cows). When he moves a cow, he may command it to go to any unoccupied integer position, as long as at its new position it is no longer an endpoint. You can see that over time, such moves can make the cows get closer and closer together. Find the minimum and maximum possible number of moves required to make the cows gather into consecutive positions.

First input an integer $N$ ($N \leq 100000$). Then input $N$ numbers, representing the positions of the $N$ cows.

The first line contains the minimum number of moves Farmer John needs to gather the cows together. The second line contains the maximum number of moves he could make while still gathering the cows together.

The first problem of the Silver Division in the February 2019 USACO contest. Translated by ChatGPT 5