3. 奶牛排序

【题目描述】

夏洛克有$n$头奶牛，每头奶牛有一个唯一的“脾气暴躁”值$a_i$。

每天晚上奶牛们都会排队挤奶，但是脾气暴躁的奶牛更容易损坏夏洛克的挤奶设备，夏洛克希望重新安排奶牛的排成一列，以便它们排成越来越脾气暴躁。

在这个过程中，任何两头奶牛(必然相邻)都可以互换，而每次互换夏洛克都需要$x+y$的时间来交换两头脾气暴躁值为$x$和$y$的奶牛。

请你帮助夏洛克计算将奶牛排好序需要的最短时间。

【输入格式】

第一行一个整数$n(n\leq 10^5)$。

接下来$n$行每行一个整数，其中第$i$行的整数$a_i(a_i\leq 10^5)$表示第$i$头牛的脾气暴躁值。

【输出格式】

一行一个整数，表示奶牛排好序需要的最短时间。

【样例输入】

3
2
3
1

【样例输出】

7

【样例说明】

开始时奶牛的顺序为：$2$ $3$ $1$。

第一次可以交换$3$和$1$，需要花费$3+1=4$的时间，奶牛顺序为：$2$ $1$ $3$。

第二次可以交换$2$和$1$，需要花费$2+1=3$的时间，奶牛顺序为：$1$ $2$ $3$。