AT_past202306_k 入れ替えてソート

There is a sequence of length $ N $ , $ P=(P_1,P_2,\ldots,P_N) $ , which is a permutation of $ (1,2,\ldots,N) $ . You can perform the following operation on this sequence any number of times, possibly zero: - Choose an integer $ i $ between $ 1 $ and $ N-1 $ , inclusive, and swap the $ i $ -th element and the $ (i+1) $ -th element of $ P $ . The cost of this operation is the sum of the two numbers being swapped. Find the minimum cost required to sort $ P $ in ascending order.

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Print the answer.

### Sample Explanation 1 For example, you can sort $ P $ in ascending order by performing the following three operations: - Choose $ i=1 $ to swap $ 3 $ and $ 2 $ . This costs $ 5 $ , and the sequence becomes $ (2,3,1,4) $ . - Choose $ i=2 $ to swap $ 3 $ and $ 1 $ . This costs $ 4 $ , and the sequence becomes $ (2,1,3,4) $ . - Choose $ i=1 $ to swap $ 2 $ and $ 1 $ . This costs $ 3 $ , and the sequence becomes $ (1,2,3,4) $ . Since it is impossible to sort the sequence in ascending order with a cost less than $ 12 $ , the answer is $ 12 $ . ### Sample Explanation 3 Sometimes, no operations are needed. ### Constraints - $ 1 \leq N \leq 2\times 10^5 $ - $ N $ is an integer. - $ P $ is a permutation of $ (1,2,\ldots,N) $ .