Sensor

在一条直线上有n个传感器，已知每个传感器的位置。现需要在这些传感器之间建立一些一对一连接。这些一对一连接是互不相同的，即同一传感器若与多个传感器建立连接，则需要建立多个一对一连接。
传感器A的传输半径定义为，与传感器A建立连接的所有传感器到A的最远距离，也就是传感器A需要多大的功率能够到达所有建立连接的传感器。
对于两个不同的传感器A和B，我们定义传感器A影响传感器B，当且仅当A和B之间的距离不超过A的传输半径。注意，A影响B并不意味着B一定影响A，因为传感器A和传感器B的半径可能是不同的。被传感器A影响的传感器数量称为传感器A的Inference。
现在请你计算一种连接方案，使得n个传感器连通，并且所有传感器的Inference之和最小。

输入包含多组数据，每组数据包含两行，第一行包含一个整数n (1 <= n <= 30)，表示传感器的数目，第二行包含n个整数，表示每个传感器的坐标位置，坐标范围是[0,1000000000(10^9)]。
输入到文件结束为止

对于每组数据，输出一行包含一个整数，表示最小可能的Inference之和。

3
1 3 7
5
3 4 2 5 1
6
1 2 4 8 16 32

4
8
13

假设我们把传感器根据输入顺序按照1, 2 …… n标号。
样例1：连接(1, 2) (2, 3)
样例2：连接(1, 2) (2, 4) (3, 1) (3, 5)
样例3：连接(1, 2) (2, 3) (2, 4) (4, 5) (4, 6)

ACRush@THU

HDOJ 5th Anniversary Contest