Background

“什么？磊哥不见了！”当ACM队员们听这个消息时，距离海上fce还有不到四天时间。

“不行，需要赶紧找到他才行。”一鸣gg站了起来。

“可是去哪儿找人？我们甚至都不知道他现在在哪里！”南雄jj问道。

“我知道。”许久没来实验室的瑶瑶突然出现在门口。她拨弄了下腕表，一幅巨大的无向图投影在实验室的中央。

“我已经知道了他目前所在的时空位置，”瑶瑶指着某个发光的点说道，“但是想要抵达这里，需要通过无数个时空隧道经过无数个世界再返回，开销太大以致于现在的我们还无法承受这个代价。” “不过还有一个办法。”瑶瑶领着众人去到励志广场，随即从四维空间口袋里拿出一艘飞船。

“这是DR.任新研发的可以穿越时间空间的飞船，具有定位功能，并且可以无视时空隧道直接进行时空折叠。不过要想驾驶这艘飞船还必须严格遵循一项规定。”瑶瑶环视众人充满疑惑却毫不畏惧的表情，缓步行至飞船门旁，“想要找到磊哥就跟我上来。”

ACM队员们没有任何犹豫，立即跟着瑶瑶上了飞船，而你则站在门外静静观望着。

Description

众人上船后却被一股神奇的力量给分隔开，排成一条长队，每个人身前都浮现出一个数字，并且所有人的数字都各不相同。

“看到前面的数字了吧，多的我就不一一解释了，现在需要你们按照从小到大依次排开。”

“那不是很简...欸，我怎么动不了了？”

“傻了吧唧的，要是有这么简单还会等到现在？”瑶瑶邪魅一笑，眼神中透露着三分薄凉，三分讥笑和四分漫不经心。“需要靠我手中的控制器才能移动你们的位置，每次只能交换两个人的位置，并且需要消耗的时空能源就是这两人身前的数字之和，这同样也是飞船穿梭时空的重要燃料。”

“那个聪明的谁来着快过来一下。”瑶瑶突然叫住站在门后的你，“我把控制器交给你，但是你需要告诉我消耗最小的燃料是多少。切记，剩余燃料越多，飞船就能越快抵达磊哥所处的时空。那个聪明的谁，你也不想让他错过比赛吧。”

盯着手中的控制器，聪明的你陷入了沉思。你知道他们所有人身前的数字以及当前所处的位置，可是要怎么交换才能让消耗的燃料最少呢？

Input

第一行输入一个整数n(1<=n<=100000)，表示当前飞船上除了你和瑶瑶以外所有ACM队员的数量。 第二行输入n个用空格隔开的正整数ai(1<=a<=1000000000)，表示当前队伍第i个人身前的数字，每个人的数字各不相同。

Output

输出一行一个整数，表示要想成功驾驶飞船所需要消耗的最少燃料量。

Samples

input1

5
5 3 2 9 4

output1

24

Limitation

1s, 256Mb

为了不让某些平行世界无法回家的磊哥回家，因此派出我们ACM队员来接他啦~