【题目描述】
为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的$N$头奶牛（方便起见，编号为$1\sim N$）进行传球。
这些奶牛在牛棚一侧沿直线排列，第$i$号奶牛位于距离牛棚$x_i$的地方。
每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。
当第$i$号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛）。
为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。
帮助他求出为了达到这一目的他开始时至少要传出的球的数量。
假设他在开始的时候能将球传给最适当的一组奶牛。

【输入格式】
输入的第一行包含$N$。
第二行包含$N$个用空格分隔的整数，其中第$i$个整数为$x_i$。

【输出格式】
输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

【数据范围】
$1\le N\le 100$
$1\le x_i\le 1000$

【输入样例】

5
7 1 3 11 4

【输出样例】

2

【样例解释】
在上面的样例中，Farmer John应该将球传给位于$x=1$的奶牛和位于$x=11$的奶牛。
位于$x=1$的奶牛会将她的球传给位于$x=3$的奶牛，在此之后这个球会在位于$x=3$的奶牛和位于$x=4$的奶牛之间来回传递。
位于$x=11$的奶牛会将她的球传给位于$x=7$的奶牛，然后球会被传给位于$x=4$的奶牛，在此之后这个球也会在位于$x=3$的奶牛和位于$x=4$的奶牛之间来回传递。
这样的话，所有的奶牛都会至少一次接到球（可能从Farmer John，也可能从另一头奶牛）。
可以看出，不存在这样一头奶牛，Farmer John可以将球传给她之后所有奶牛最终都能被传到球。

【分析】

---

一头牛的球只能传给另一头牛，如果左边的牛距离更近或者和右边的牛距离相等则传给左边，否则传给右边；一头牛最多可以接到两个牛传来的求，即左边和右边的牛传来的。将牛看成点，传球看成有向边，则可以构成一个基环树的图，每个点的出度为$1$，入度为$0\sim 2$，因此球要么单向地往某一个方向传，要么就会形成一个两个点的环，如下图所示：

入度为$0$的点必须得给他传球，否则就不会有球传给他，因此需要传的球数$+1$；当一个球传两次后，即某一点$i$的下一个点$j$的再下一个点为他本身时，说明这个点在环中，如果这个环的两个点都没有挂载一棵树（即$i,j$入度都为$1$），那么需要给这个环的任意一个点传一次球，即对于其中一个点来说，传球数$+1/2$。在求解的时候将第一种情况的传球数记为$+2$，第二种情况记为$+1$，最后将结果除以二即可。

---

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 110, INF = 0x3f3f3f3f;
int x[N], to[N], in[N];//to表示会把球传给谁,in表示每个点的入度
int n, res;int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> x[i];x[0] = -INF, x[n + 1] = INF;sort(x, x + n + 2);for (int i = 1; i <= n; i++)if (x[i] - x[i - 1] <= x[i + 1] - x[i]) to[i] = i - 1, in[i - 1]++;else to[i] = i + 1, in[i + 1]++;for (int i = 1; i <= n; i++)if (!in[i]) res += 2;else if (to[to[i]] == i && in[i] == 1 && in[to[i]] == 1) res++;cout << res / 2 << endl;return 0;
}