let quick_sort a cmp =
  let rec partition p r =
    let swap i j = let t = a.(i) in a.(i) <- a.(j); a.(j) <- t
    in
    let rec exchange i j =
      if j >= r then (swap (i + 1) r; i + 1)
      else if cmp a.(j) a.(r) <= 0 then (swap (i + 1) j; exchange (i + 1) (j + 1))
      else exchange i (j + 1)
    in exchange (p - 1) p
  and doit p r =
    if p < r then begin
      let q = partition p r in
      doit p (q - 1);
      doit q r
    end in
  doit 0 (Array.length a - 1)

let calc_cost a n =
  let b = Array.copy a in
  quick_sort b compare;
  let min_a = b.(0) in
  let max_a = b.(n - 1) in
  let b_i = Array.make (max_a + 1) 0 in
  Array.iteri (fun i e -> b_i.(e) <- i) b;
  let v = Array.make n false in
  let rec doit i cost =
    if i = n then cost
    else if v.(i) then doit (i + 1) cost
    else begin
      let rec aux j ws =
        v.(j) <- true;
        let w = a.(j) in
        if v.(b_i.(w)) then w :: ws
        else aux b_i.(w) (w :: ws)
      in
      let ws = aux i [] in
      let n_w = List.length ws in
      let sum_w = List.fold_left (+) 0 ws in
      let min_w = List.fold_left min max_a ws in
      doit (i + 1) (cost + (min (sum_w + (n_w - 2) * min_w) (sum_w + min_w + (n_w + 1) * min_a)))
    end in
  doit 0 0

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun e -> e)) in
  Printf.printf "%d\n" (calc_cost a n)