鱼儿子的反击

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

鱼头终于在你的帮助下,在下棋上战胜了自己的儿子,大呼得意。于是,鱼儿子决定要挫挫爸爸的锐气,给爸爸出了道难题。 连续的整数如图排列,这些数字一定在int范围内。给出其中的N个点的数字(N<=100),鱼头需要在这N个点中建立路径,使任意一个点可以直接或间接的与另外N-1个点连通,路径为每跨越一条边算长度1,只能从从边走,不能从点走。求建立这些连接所需要的最短路径总长度。鱼头又囧了,只能偷偷的打电话让你给出他答案,电话费很贵的,赶紧搞定告诉可怜的鱼头吧。 输入:多组测试数据以文件尾结束。第一行为一个整数N。下面的N行分别只有一个数,代表上面三角形的一个数字,来表示位置。 输出:建立这些点之间连接的最短路径总长度。

Input

多组测试数据以文件尾结束。第一行为一个整数N。下面的N行分别只有一个数,代表上面三角形的一个数字,来表示位置。

Output

建立这些点之间连接的最短路径总长度。

Sample Input

2
6
12

Sample Output

3

Hint

Source

DouYuFeng

提交代码