题目描述

现在有一个警察抓小偷的游戏，塔子哥刚好玩到让小偷跑到了一个长长的桥面上去。

假设在桥面上，有$N$块紧密相连的桥板。标号1~$N$，小偷已经逃到了标号为$K$的桥板上。现在， 塔子哥可以用超能力拆除一些桥板来使得小偷掉落河中，然而他无法拆除小偷所踩的桥板$K$。每个桥板拆除时都需要支付不同的代价$Aᵢ$，当桥体两侧的桥板都没有与河两岸连接时，则桥和小偷会一起掉落到河中。

求塔子哥需要支付的最小代价。

假设某一情况如图：

桥体1和桥体4可以通过分别支付8和3的代价来拆除，此时小偷所在的桥板2和桥板3一起掉落河中。因此最小代价为11.

输入描述

第一行给出$N$， 表示冰块的数量。 第二行中，按顺序给出代表打破第i块冰块所需的力的$Aᵢ$。 题目保证企鹅所在的地方用$-1$表示， 没有企鹅位于冰块$1$或冰块$N$的情况。 $3≤N≤2*10⁵,1≤Aᵢ≤10⁹$

输出描述

输出可以将企鹅击落到水中的最小力。

示例1

输入

5
8 -1 7 3 6

输出

11

说明

见题目举例

示例2

输入

10
49 46 -1 55 54 53 52 51 50 51

输出

96

说明 打破桥面2和桥面9， 最小代价为46+50=96