Hoofball#10406
In preparation for the upcoming hoofball tournament, Farmer John is drilling his cows (conveniently numbered 1, \ldots, n) on passing the ball. The cows are standing in a very long line on one side of the barn, with cow standing x_i units away from the barn. All cows stand at distinct positions.
At the beginning of the drill, Farmer John will pass several balls to different cows. Whenever cow receives a ball, either from Farmer John or from another cow, she passes it to the cow nearest to her. If several cows are at the same distance from her, she passes the ball to the leftmost of them. To give every cow at least a little passing practice, Farmer John wants to make sure that each cow holds a ball at least once. Help him find the minimum number of balls he needs to hand out initially to achieve this, assuming he chooses an appropriate initial set of cows to receive them.
The first line contains the integer n~(1 \le n \le 100). The second line contains integers, where the -th integer is x_i~(1 \le x_i \le 1000).
Print the minimum number of balls Farmer John must initially pass to the cows so that every cow holds a ball at least once.
In the example, Farmer John should pass one ball to the cow at x = 1 and another ball to the cow at x = 11. The cow at x = 1 passes her ball to the cow at x = 3, after which this ball keeps bouncing back and forth between the cows at x = 3 and x = 4. The cow at x = 11 passes her ball to the cow at x = 7, who passes it to the cow at x = 4, after which this ball also keeps bouncing between the cows at x = 3 and x = 4. Thus every cow receives a ball at least once, either from Farmer John or from another cow.
It is easy to see that there is no single cow to whom Farmer John could pass one ball so that every cow would eventually receive it.
Example 1