use std::collections::VecDeque;
use std::env;
//use std::fmt::Debug;
use std::io;
use std::cmp;
use std::io::prelude::*;
//use std::time::{Duration, Instant};

//===================================================
// MACROs need to be defined above the use place ... ?
macro_rules! dprintln {
    ($($x:expr),*) => {{
        if $crate::is_debug_mode() {
            let f = || {println!( $($x),*)};
            f() } }} }

/// Backward For-Loop Helper
///  from -> to (exclude `to`)
/// # Examples
/// see tests::macro_backward()
#[macro_export]
macro_rules! backward_ho {
    ($from:expr, $to:expr) => {{
        (($to + 1)..($from + 1)).rev() }}; }
//===================================================

#[derive(Debug)]
struct Quiz {
    n: usize,    // 1 <= N <= 1,000
    v: Vec<u32>, // 1 <= v[i] <= 10,000, length=N
}

#[derive(Debug)]
struct Answer {
    min_cost: u64
}

trait IntoQuiz {
    fn into_quiz(self) -> Quiz;
}

impl<I: Input> IntoQuiz for I {
    fn into_quiz(mut self) -> Quiz {
        let n: usize = self.parse_next().unwrap();
        let v: Vec<u32> = self.parse_next_vec(n).unwrap();
        Quiz { n, v }
    }
}

#[derive(Debug,Clone)]
struct SortGroup {
    min: u32,
    elems: Vec<u32>,
    connect_cost: u64,
}

impl SortGroup {
    pub fn new() -> Self {
        SortGroup {
            min: std::u32::MAX,
            elems: Vec::new(),
            connect_cost: 0u64,
        }
    }

    pub fn add(&mut self, c: u32) {
        dprintln!(" SG.add {}", c);
        self.min = cmp::min(self.min, c);
        self.elems.push(c);
    }

    pub fn cost(&self) -> u64 {
        let c = self.elems.len() as u64;

        if c <= 1 {
            return 0;
        }

        let mut sum = self.elems.iter().fold(0u64, |s, e| s+(*e as u64));
        sum += (c-2)*self.min as u64;

        dprintln!(" [cost{:?}] {}", self, sum);

        sum + self.connect_cost
    }

    pub fn connect(self, other: Self) -> Self {
        let other_elems = other.elems.into_iter();
        let mut elems: Vec<u32> = self.elems.into_iter().chain(other_elems).collect();
        let mut min = cmp::min(self.min, other.min);

        SortGroup {
            min: min,
            elems: elems,
            connect_cost: self.connect_cost + (self.min + other.min) as u64,
        }
    }
}

impl Quiz {
    fn solve(self) -> Answer {
        let mut v = {
            let mut t = self.v.to_vec()
                .into_iter()
                .enumerate()
                .map(|(n,x)| (x,n));
            let mut vt = t.collect::<Vec<_>>();
            vt.sort();
            let mut vtt: Vec<Option<(usize, (u32, usize))>> = vt.into_iter().enumerate().map(|x| Some(x)).collect();
            vtt
        };

        let mut gs = Vec::new();
        let mut g_min : Option<SortGroup> = None;
        for i in 0usize..v.len() {
            dprintln!(" {:?}", v[i]);
            let mut g = SortGroup::new();

            if let Some((_dst, (c, src))) = v[i].take() {
                let mut next_i = src;
                g.add(c);
                dprintln!(" -> {:?}", v[next_i]);

                while let Some((_dst2, (c2, src2))) = v[next_i].take() {
                    next_i = src2;
                    g.add(c2);
                    dprintln!(" -> {:?}", v[next_i]);
                }
                dprintln!("  g: {:?}", g);

                if let Some(gt) = g_min.take() {
                    if gt.min > g.min {
                        gs.push(gt);
                        g_min = Some(g);
                    } else {
                        gs.push(g);
                        g_min = Some(gt);
                    }
                } else {
                    g_min = Some(g);
                }
                dprintln!(" g_min {:?}", g_min);
            }
        }

        dprintln!("=== Making Groups Result ===");
        dprintln!("group: ");
        dprintln!(" {:?}", gs);
        dprintln!("min: {:?}", g_min);

        let mut rest_sum = 0u64;
        if let Some(gtt) = g_min.take() {
            let mut gt = gtt;
            for g in gs {
                let y = gt.min as i32;
                let x = g.min as i32;
                let c = g.elems.len() as i32;

                if y * (c+1) < x * (c-3) {
                    dprintln!(" connect {:?} + {:?}", gt, g);
                    gt = gt.connect(g);
                } else {
                    dprintln!(" not connect {:?}, {:?}", gt, g);
                    gt = gt;
                    rest_sum += g.cost();
                }
            }

            g_min = Some(gt);
        }

        if let Some(gt) = g_min.take() {
            Answer {
                min_cost: gt.cost() + rest_sum,
            }
        } else {
            panic!("No elems");
        }
    }
}

impl Answer {
    fn print(self) {
        println!("{}", self.min_cost);
    }
}

// =====================================================
// = Lib
// =====================================================

//==================================================
// Main
fn main() {
    // Initialize
    set_debug_mode(false);
    for arg in env::args() {
        if arg == "--debug" {
            set_debug_mode(true);
        }
    }
    dprintln!("[DebugMode] {}", "On");

    // Execute
    dprintln!("=================");
    dprintln!("= READ INPUT     ");
    let stdin = io::stdin();
    let input = BufReadInput::new(stdin.lock());
    dprintln!("[Input] \n{:?}", input);
    dprintln!("=================");
    dprintln!("= INTERPRET INPUT");
    let q = input.into_quiz();
    dprintln!("[Quiz] \n{:?}", q);
    dprintln!("=================");
    dprintln!("= SOLVE QUIZE    ");
    let a = q.solve();
    dprintln!("[Answer] \n{:?}", a);
    dprintln!("=================");
    dprintln!("= PRINT ANSWER   ");
    a.print();
    dprintln!("=================");
}

//==================================================
// Stdin Reader
#[derive(Debug)]
pub enum Token {
    Word(String),
    LineBreak,
}

impl Token {
    pub fn is_word(&self) -> bool {
        match *self {
            Token::Word(ref _x) => true,
            _ => false,
        }
    }
}

#[derive(Debug)]
pub struct BufReadInput<R: BufRead> {
    input: R,
    tokens: VecDeque<Token>,
}

pub trait Input {
    fn read_next_word(&mut self) -> Option<Token>;

    fn parse_next<T>(&mut self) -> Option<T>
    where
        T: std::str::FromStr,
    {
        if let Some(Token::Word(str)) = self.read_next_word() {
            match str.parse() {
                Ok(x) => Some(x),
                _ => None,
            }
        } else {
            None
        }
    }

    fn parse_next_vec<T>(&mut self, size: usize) -> Option<Vec<T>>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::new();

        for _i in 0..size {
            if let Some(t) = self.parse_next() {
                v.push(t);
            } else {
                return None;
            }
        }

        Some(v)
    }

    fn parse_next_vec2<T>(&mut self, size2: usize, size1: usize) -> Option<Vec<Vec<T>>>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::new();

        for _i in 0..size2 {
            if let Some(t) = self.parse_next_vec(size1) {
                v.push(t);
            } else {
                return None;
            }
        }

        Some(v)
    }

    fn parse_all_remaining_into_vec<T>(&mut self) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::new();

        loop {
            match self.parse_next() {
                Some(x) => v.push(x),
                None => return v,
            }
        }
    }
}
impl<R: BufRead> BufReadInput<R> {
    pub fn new(input: R) -> Self {
        let tokens = VecDeque::new();

        BufReadInput { input, tokens }
    }
}

impl<R: BufRead> Input for BufReadInput<R> {
    fn read_next_word(&mut self) -> Option<Token> {
        loop {
            match self.tokens.pop_front() {
                None => {
                    // Read Input
                    let mut line = String::new();
                    let n = self.input.read_line(&mut line).expect("Read Error.");
                    if n == 0 {
                        return None;
                    }
                    let mut line_tokens = tokenaize(line);
                    self.tokens.append(&mut line_tokens);
                }
                Some(Token::LineBreak) => (),
                x => return x,
            }
        }
    }

}

//TODO: Make CaseIterator
// ex) 
//  let mut input: Input ...
//  let mut iter: CaseIterator<Case=Command> = input.rest_into_cases(|i|   
//    let cmd:String = i.parse_next().expect("Parse error cmd");
//    let num:u32    = i.parse_next().expect("Parse error num");
//
//    Command::new(cmd, num)
//  );
//  let case1 = iter.next();
//  let case2 = iter.next();
//  ...


fn tokenaize(str: String) -> VecDeque<Token> {
    let mut v = VecDeque::new();

    for w in str.split_whitespace() {
        v.push_back(Token::Word(w.to_string()));
    }
    v.push_back(Token::LineBreak);
    v
}

//==================================================
// Utility
pub fn concat_vec_to_string<T>(v: &Vec<T>) -> String
where
    T: std::fmt::Display,
{
    let mut string = String::with_capacity(v.len() * 2);

    if let Some((h, t)) = v.split_first() {
        string = h.to_string();

        for obj in t {
            string.push(' ');
            string.push_str(&obj.to_string());
        }
    }

    return string;
}

struct Step {
    current: i64,
    start: usize,
    end: usize,
    step: i32,
}

impl Step {
    fn new(start: usize, end: usize, step: i32) -> Self {
        if step == 0 {
            panic!("step can't be 0");
        } else if step > 0 && start > end {
            panic!("Can't reach end.");
        } else if step < 0 && start < end {
            panic!("Can't reach end.");
        } 

        Step {
            current: start as i64,
            start: start,
            end: end,
            step: step,
        }
    }
}

impl Iterator for Step {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        let current_is_enable = if self.step > 0 {
            self.current <= self.end as i64
        } else {
            self.current >= self.end as i64
        };

        if !current_is_enable {
            None
        } else {
            let ret = self.current as usize;
            self.current += self.step as i64;
            Some(ret)
        }
    }
}

//==================================================
// Debug Switch
static mut S_DEBUG_MODE: bool = false;
fn is_debug_mode() -> bool {
    unsafe { S_DEBUG_MODE }
}

fn set_debug_mode(mode: bool) {
    unsafe {
        S_DEBUG_MODE = mode;
    }
}

//==================================================
// Usage
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn macro_backward() {
        let mut v = Vec::new();
        for i in backward_ho!(5, 1) {
            v.push(i);
        }
        assert_eq!(vec![5, 4, 3, 2], v);
    }

    #[test]
    fn step_basis() {
        let step = Step::new(0, 6, 2);
        let v: Vec<usize> = step.collect(); 
        assert_eq!(vec![0, 2, 4, 6], v);

        let step = Step::new(0, 5, 3);
        let v: Vec<usize> = step.collect(); 
        assert_eq!(vec![0, 3], v);

        let step = Step::new(5, 0, -1);
        let v: Vec<usize> = step.collect(); 
        assert_eq!(vec![5,4,3,2,1,0], v);

        let step = Step::new(5, 4, -2);
        let v: Vec<usize> = step.collect(); 
        assert_eq!(vec![5], v);
        
        let step = Step::new(100, 100, 1);
        let v: Vec<usize> = step.collect(); 
        assert!(v.is_empty());
    }
}



Measured memory_bytes: 5068