Description

Xiao C has an integer sequence of $N$ numbers, in which all numbers are pairwise distinct.

Each time, Xiao C can swap any two numbers in the sequence, with a cost equal to the sum of those two numbers.

Xiao C wants to sort the entire sequence in ascending order. What is the minimal cost needed?

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers, representing Xiao C's sequence.

Output Format

Output one line containing an integer, the minimal cost Xiao C needs.

6
8 4 5 3 2 7

34

Hint

• For $30\%$ of the testdata, $N\le10$.
• For $100\%$ of the testdata, $1\le N\le10^5$, and the $N$ integers on the second line are positive integers not exceeding $10^9$.

Translated by ChatGPT 5