题目内容

塔子哥住的小区前面有一条公路，在公路上有一排 $n$ 个居民楼，每个居民楼都有一个高度，第 $i$ 个居民楼的高度为 $a_i$ ，相邻居民楼都相隔 $100$ 米，塔子哥最近回家的时候经常没有路灯，然后经常迷路，现在塔子哥想在想要是公路左右两边各设计一座灯塔，这样灯塔就可以把所有地方都照亮，塔子哥回家路上就不会迷路了，现在塔子哥想知道灯塔至少得有多高。

为了简化问题，公路可看做一条直线， 居民楼和灯塔可看做立在公路旁边的一条竖线，左边的灯塔距离最左边的居民楼和右边灯塔距离最右边的居民楼也都是 $100$ 米。居民楼会挡住灯光，如果从最左边的居民楼到最右边的居民楼中间的点都要至少要被一座灯塔照亮， 那么两座灯塔高度之和最少是多少。

输入描述

第一行输入 $N$ ( $2\le N\le 100$ )，代表居民楼数量

第二行有 $N$ 个整数，第 $i$ 个整数代表从左到右第 $1$ 座居民楼的高度，居民楼高度在 $[1，100]$ 米范围内

输出描述

输出从最左边的居民楼到最右边的居民楼中间的点都要至少要被一座灯塔照亮， 所需要的两座灯塔高度之和的最小值，值为整数。

样例

样例一：

输入

2
100 100

输出

600

样例二：

输入

3
100 90 80

输出

738