P1677 [USACO18FEB] Hoofball B

To prepare for the upcoming hoofball tournament, Farmer John is training his $N$ cows (for convenience, numbered $1\ldots N$, where $1\le N\le 100$) to pass balls. The cows are standing in a line along one side of the barn; cow $i$ is located at position $x_i$ away from the barn ($1\le x_i\le 1000$). Each cow is at a distinct position. At the start of training, Farmer John will throw some number of balls to different cows. When cow $i$ receives a ball, whether from Farmer John or from another cow, she will pass the ball to the nearest cow (if there are multiple cows at the same distance from her, she will pass it to the one with the smaller $x_i$). To ensure every cow gets a chance to practice passing, Farmer John wants to make sure that every cow holds a ball at least once. Help him compute the minimum number of balls he must throw at the beginning to achieve this goal. Assume that at the beginning he can throw balls to the best possible set of cows.

The first line contains $N$. The second line contains $N$ space-separated integers, where the $i$-th integer is $x_i$.

Output the minimum number of balls Farmer John must throw at the beginning so that every cow holds a ball at least once.

In the sample above, Farmer John should throw balls to the cow at $x=1$ and the cow at $x=11$. The cow at $x=1$ will pass her ball to the cow at $x=3$, and after that this ball will be passed back and forth between the cow at $x=3$ and the cow at $x=4$. The cow at $x=11$ will pass her ball to the cow at $x=7$, then the ball will be passed to the cow at $x=4$, and after that this ball will also be passed back and forth between the cow at $x=3$ and the cow at $x=4$. In this way, all cows will receive a ball at least once (either from Farmer John or from another cow). It can be seen that there is no single cow such that, if Farmer John throws a ball to her, then eventually all cows will end up receiving a ball. Translated by ChatGPT 5