You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times.

Write a program which reports the minimal total cost to sort the given integers.

Constraints

* $1 \leq n \leq 1,000$
* $0 \leq w_i\leq 10^4$
* $w_i$ are all different

Input

In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given.

Output

Print the minimal cost in a line.

Examples

Input

5
1 5 3 4 2


Output

7


Input

4
4 3 2 1


Output

10
n = gets.chomp.to_i
t = []
arr = gets.chomp.split.map(&:to_i)
n.times do |i|
  t << arr.shift
end


def swap(list, a, b)
  list[a], list[b] = list[b], list[a]
  return list
end

def minCostPath(list)
  before = (0..list.size-1).to_a
  sorted = list.sort
  after = []
  list.each do |item|
    after << sorted.index(item) 
  end
  s = 20000
  idx1, idx2 = 0
  p list
  p before
  p after
  before.zip(after).each  do |bef,aft|
    unless bef == aft
      sum = list[bef] + list[aft]  
      if sum < s
        s = sum
        idx1 = bef
        idx2 = aft
      end
    end
  end

  return idx1, idx2, s
end

total = 0

while true
  i, j, s = minCostPath(t)
  puts i,j,s
  break if s == 20000
  total += s
  p "total: #{total} p #{t}"
  t = swap(t, i,j)
end
p total