Cho 1 dãy số nguyên dương cần sắp xếp dãy số đó theo thứ tự tăng dần. Để sắp xếp thì cần thao tác hoán đổi vị trí của 2 số và chi phí cho sự hoán đổi chính là tổng của 2 số đó.

Yêu cầu: Cho biết chi phí thấp nhất để sắp xếp dãy số đã cho theo thứ tự tăng dần.

Dữ liệu vào:

• Có nhiều bộ test, mỗi bộ test gồm 2 dòng.
• Dòng 1: Số lượng số nguyên dương trong dãy số \(n\) (với \(n \gt 1\)).
• Dòng 2: \(n\) số nguyên dương (nhỏ hơn \(1000\)) của dãy cách nhau bởi khoảng trắng.
• Input kết thúc với dòng chỉ chứa số \(0\) và không cần xử lý.

Dữ liệu ra:

• Với mỗi bộ test, output chi phí thấp nhất để sắp xếp dãy số đã cho theo thứ tự tăng dần trên 1 dòng riêng.

Input

3
3 2 1
4
8 1 2 4
5
1 8 9 7 6
6
8 4 5 3 2 7
0

Output

4
17
41
34