1738. 蹄球
为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N）进行传球。
这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 xi 的地方。
每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。
当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛。）。
为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。
帮助他求出为了达到这一目的他开始时至少要传出的球的数量。
假设他在开始的时候能将球传给最适当的一组奶牛。
输入格式
输入的第一行包含 N。
第二行包含 N 个用空格分隔的整数，其中第 i 个整数为 xi。
输出格式
输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
数据范围
1≤N≤100,
1≤xi≤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 可以将球传给她之后所有奶牛最终都能被传到球。
代码：
/*
然后就发现——
由于每个点只能传给离它距离最近的一个点，所以可以证明每个点只有一个出度。而对于入度为0的点，就一定要作为发球点（不作为发球点，那谁能传给它阿）。
另外，这只是充分条件，并不是必要条件（即入度为0 -> 它是发球点 ，但不代表它是发球点 -> 入度为0）
因为有可能是两个点，互相作为最短距离，虽然入度没有为0的，但这种“环”也要算进去
（因为每个点只能连接相邻的边，所以不可能有三个点以上的环呀。环只有A->B，B->A的情况，很轻松就能判断，不需要建边。知道这个方面就很容易就能写出来代码了）所以我们按每个点顺序扫一遍它的最短距离是谁，然后再找到入度为0的点以及“环”即可
*/
#include <bits/stdc++.h>
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 110;
int q[N], p[N], d[N];
int n;int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> q[i];q[0] = -INF, q[n + 1] = INF;sort(q + 1, q + n + 1);for (int i = 1; i <= n; i++)if (q[i] - q[i - 1] <= q[i + 1] - q[i]){p[i] = i - 1;d[i - 1]++;}else{p[i] = i + 1;d[i + 1]++;}int res = 0;for (int i = 1; i <= n; i++){if (d[i] == 0)res += 2;else if (d[i] == 1 && p[p[i]] == i && d[p[i]] == 1)res += 1;}cout << res / 2;return 0;
}