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
package main

/*
最小コストソート
*/

import (
	"bufio"
	"bytes"
	"fmt"
	"log"
	"os"
	"strconv"
	"strings"
)

func partition(a []int) int {
	x := a[len(a)-1]
	i := -1
	for j := 0; j < len(a)-1; j++ {
		if a[j] <= x {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[len(a)-1] = a[len(a)-1], a[i+1]
	return i + 1
}
func quickSort(a []int) {
	if len(a) > 1 {
		q := partition(a)
		quickSort(a[:q])
		quickSort(a[q+1:])
	}
}

func countCost1(a, sorted []int) int {
	cost := 0
	for i := len(a) - 1; i > 0; i-- {
		if sorted[i] == a[i] {
			continue
		}
		for j := i - 1; j >= 0; j-- {
			if sorted[i] == a[j] {
				a[i], a[j] = a[j], a[i]
				cost = cost + a[i] + a[j]
			}
		}
	}
	return cost
}
func countCost(a []int) int {
	b := make([]int, len(a))
	copy(b, a)
	quickSort(b)
	return countCost1(a, b)
}

func main() {
	scanner := makeScanner(6 * 1000)
	eGetInt(scanner)
	integers := eGetInts(scanner)
	fmt.Println(countCost(integers))
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}

type ints []int

func (s ints) String() string {
	var buf bytes.Buffer
	sep := ""
	for _, v := range s {
		buf.WriteString(fmt.Sprintf("%s%d", sep, v))
		sep = " "
	}
	return buf.String()
}

func reverse(a ints) ints {
	r := make(ints, len(a))
	for i := 0; i < len(a); i++ {
		r[i] = a[len(a)-1-i]
	}
	return r
}
func max(a ints) (int, bool) {
	if len(a) == 0 {
		return 0, false
	}
	m := a[0]
	for _, e := range a {
		if e > m {
			m = e
		}
	}
	return m, true
}
func sum(a ints) int {
	if len(a) == 0 {
		return 0
	}
	sum := 0
	for _, e := range a {
		sum += e
	}
	return sum
}

