题目描述

有n个目标点,你需要放k个人,使所有目标点都移动得到。

所有人移动时为了节约时间,都会往最近的点移动。

现在你知道这些人的位置,求k的最小值。

输入格式

第1行1个数,n。表示有多少个目标点。

接下来n个数,表示每个人的位置。

输出格式

1个数,k。

输入输出样例

输入 #1复制

5

7 1 3 11 4
输出 #1复制
2

说明/提示

样例解释#1:可以放在1和3号。

位于1的人可以移动到移动到(数字表示下标):1,2,4。

位于3的人可以移动到:0,3。

位于1的人在3,4中间循环移动。

对于第i个测试点,n=10×i (i<9),n=85(i=9),n=100(i=10)

测试点分值:4,5,6,9,10,11,14,15,16,20