Description

众所周知，ACfun的群主很牛逼,把960万平方公里的傻逼网友全拉到一个群里了

王神仙加入进了ACfun群，一开始她有一个数$x$可以随你定， 接下来$n$分钟，每分钟她可以对这个数进行一次修改操作，也可以不进行，修改操作为给这个数加上一个值$y$并满足$y=1$或者$y=-1$，同时也要保证第$i$分钟后的数小于等于$a_i$

设$b_i$为$i$分钟后的数，定义一个序列$b$的权值 $S(b)=\sum\limits_{i=1}^{n}b_i$

她需要最大化$S(b)$。

但是傻逼网友萌算法实力强劲看完题就秒了，于是再加了一个条件：可以修改某一个$a_i$。

输出最大的$S(b)$的值即可。

Format

Input

第一行一个正整数 $n$ ，含 义同题面描述。

第二行共 $n$ 个正整数，第 $i$ 个表示 $a_i$，含义同题面描述。

Output

输出一行一个整数表示最大

$S(b)$，保证至少存在一个 $b$ 满足条件 。

Samples

3
4 3 2

11

Hint

$b=\{4,3,4\}$

$S(b)=4+3+4=11$

DataSize

对于 $30\%$ 的数据： $n \leqslant 10$

对于 $50\%$ 的数据： $n \leqslant 300$

对于 $70\%$ 的数据： $n \leqslant 5000$

对于 $100\%$ 的数据： $n \leqslant 200000,a_i \leqslant 1000000$