module module_sort
    use iso_fortran_env
    implicit none

    interface quicksort
        module procedure :: int32_qsort
        module procedure :: int64_qsort
    end interface quicksort
contains

    recursive function int32_qsort(m) result(res)
        integer(int32), intent(in) :: m(:)
        integer(int32) :: n, pm, pn, pv, res(size(m))

        n = size( m, 1 )

        if (n <= 1) then
          res = m
        else
          pv = m( n/2 )
          pm = max( m(1), m(n) )
          pn = min( m(1), m(n) )
          if ( pv > pm ) pv = pm
          if ( pv < pn ) pv = pn
          res = [ int32_qsort( pack(m(:), m(:) > pv) ), &
                               pack(m(:), m(:) == pv), &
                  int32_qsort( pack(m(:), m(:) < pv) ) ]
        endif

    end function int32_qsort

    recursive function int64_qsort(m) result(res)
        integer(int64), intent(in) :: m(:)
        integer(int64) :: n, pm, pn, pv, res(size(m))

        n = size( m, 1 )

        if (n <= 1) then
          res = m
        else
          pv = m( n/2 )
          pm = max( m(1), m(n) )
          pn = min( m(1), m(n) )
          if ( pv > pm ) pv = pm
          if ( pv < pn ) pv = pn
          res = [ int64_qsort( pack(m(:), m(:) > pv) ), &
                               pack(m(:), m(:) == pv), &
                  int64_qsort( pack(m(:), m(:) < pv) ) ]
        endif

    end function int64_qsort

end module module_sort

program main
    use module_sort
    use iso_fortran_env
    implicit none
    integer(int64) :: n
    integer(int64), allocatable :: ai(:)
    integer(int64) :: i, ie
    integer(int64) :: ans

    read *, n
    allocate( ai(n) )
    read *, ai( 1:n )
    ai = quicksort( ai )

    if ( mod((n-1), 2) == 0 ) then
        ie = (n-1) / 2
        ans = ai(1) + ai(ie + 1)
    else
        ie = n / 2
        ans = ai(1)
    endif

    do i = 2, ie
        ans = ans + ai(i) * 2
    enddo

    print *, ans

end program main