발굽 축구

곧 열리는 발굽 축구 대회를 앞두고 농부 존은 소 $N$마리에게 공 패스를 연습시킨다. 소에는 $1$번부터 $N$번까지 번호가 붙어 있고, $1 \leq N \leq 100$이다. 소는 모두 헛간 한쪽에 뻗은 아주 긴 직선 위에 서 있으며, $i$번 소는 헛간에서 $x_i$만큼 떨어진 지점에 서 있다 ($1 \leq x_i \leq 1000$). 두 소가 같은 지점에 서 있는 경우는 없다.

$i$번 소는 농부 존에게서든 다른 소에게서든 공을 받으면 자기와 가장 가까운 소에게 공을 넘긴다. 가장 가까운 소가 여럿이면 그중 가장 왼쪽에 있는 소에게 넘긴다. 모든 소가 패스를 조금이라도 연습하도록, 농부 존은 소마다 최소 한 번은 공을 잡게 하려고 한다. 처음에 공을 받을 소를 적절히 고를 수 있다고 할 때, 농부 존이 처음에 나눠 주어야 하는 공의 최소 개수를 구하라.

첫째 줄에 $N$이 주어진다. 둘째 줄에 정수 $N$개가 공백으로 구분되어 주어지며, $i$번째 정수가 $x_i$이다.

모든 소가 최소 한 번은 공을 잡게 하려고 농부 존이 처음에 나눠 주어야 하는 공의 최소 개수를 출력한다.

$N = 5$이고 소가 각각 $x = 7, 1, 3, 11, 4$에 서 있는 경우를 보자. 농부 존은 $x = 1$의 소와 $x = 11$의 소에게 공을 하나씩 주면 된다. $x = 1$의 소는 $x = 3$의 소에게 공을 넘기고, 그다음부터 이 공은 $x = 3$의 소와 $x = 4$의 소 사이를 오간다. $x = 11$의 소는 $x = 7$의 소에게 넘기고, $x = 7$의 소는 $x = 4$의 소에게 넘기며, 이 공도 이후에는 $x = 3$과 $x = 4$ 사이를 오간다. 이렇게 하면 농부 존에게서든 다른 소에게서든 모든 소가 최소 한 번은 공을 받는다.

한편 어느 소 한 마리에게만 공을 주어서는 모든 소가 공을 받게 만들 수 없다.