题目描述

宁宁有一个序列 a[1], a[2], ..., a[n],每次可以交换相邻的两个元素,“代价”为两个元素中较大的那个。
请问,要通过交换将序列变为从小到大递增的序列,总“代价”最少为多少？

输入格式

输入一行包含一个整数 n ,表示序列长度。
第二行包含 n 个整数,表示给定的序列。

输出格式

输出一行包含一个整数,表示最少代价的值。

样例

样例 1

输入 # 1

样例

样例 1

输入 # 1

4
1 5 2 1

输出 # 1

12