忙死了忙死了，一群调皮的孩子又不按时睡觉了，现在你必须要让他们回到自己的房间去睡觉。
宿舍里有N个孩子，每个孩子都有一个房间，所有房间排成一条直线。
房间是这样安排给孩子的，体重越重的孩子越要往后边的房间住，也就是说，对于每个房间的孩子，他的所有左边的房间的每个孩子都没他重，他的所有右边的房间的每个孩子都比他重。
且每一个孩子的体重都是不同的。
现在，有些孩子没待在自己的房间，且每个房间只有一个孩子。现在你要把他们都抱回自己的房间去，抱一个体重为X的孩子要消耗X的体能。
还有一个条件就是，当你把一个孩子从房间x抱到房间y后，必须马上要把房间y里的那个孩子抱到房间x。

也就是说你一次要交换两个房间里的孩子。

输入一个正整数N表示有N个孩子(1 <= N <= 1000)。
接下来一行有N个正整数X，代表孩子的体重(1 <= X <= 1000)。

输出你至少要消耗的体能。