题目描述

小明最近在上化学课，他需要使用到n种化学物质来进行他的实验。在做实验的时候，他需要将所有化学物质放在桌面上，按次序排成一条直线。然而每一种化学物质都是危险品，对于第i个化学物质，如果有另外一个化学物质距离它的距离小于a_i，那么就会发生爆炸。

小明想知道如果要安全的完成他的实验，桌子最短可以多短。

输入格式

第一行一个整数n，表示化学物质的个数。

第二行有n个整数，第i个整数a_i表示第i个化学物质必须与其他化学物质保持的距离。

输出格式

输出一行，包括一个整数，表示能够让小明安全完成实验的桌子最小长度。

注意：物品要按原来的次序摆放。

输入样例 #1

3
3 1 2

输出样例 #1

5

输入样例 #2

1
100000

输出样例 #2

0

输入样例 #3

5
1 9 2 8 3

输出样例 #3

34

数据范围

20% 的数据，1≤n≤20

50% 的数据，1≤n≤100000

100% 的数据，1≤n≤1000000，1≤a_i≤100000