MODULE intQsortMod
! 整数型のクイックソート
! precisionで整数の精度を定める．
! インデックスの小さいほうが値も小さい(昇順)．

! 参考
! https://t.doujin-constant.net/post/143374686394/fortranをより使いこなしたquick-sort

      implicit none
      integer,parameter,private :: precision = 16
      
      interface qSort
        module procedure :: intQsort
      end interface
      
      contains
      pure recursive function intQsort( a ) result( r )
        implicit none
        integer(precision), intent(in) :: a(:)
        integer(precision) :: r( size(a) )
        integer(precision) :: sample(3), len, i,j
        
        len = size( a(:) )
        if( len<=1 )then
          r = a
        else
          !select pivot
          sample(1:3) = [a(1), a(len/2), a(len)]
          do i = 1,2
            do j = 2,3
              if( sample(i)>sample(j) )then
                len = sample(i) !len is buffer
                sample(i) = sample(j)
                sample(j) = len
              end if
            end do
          end do
          
          r = [ qSort( pack(a(:), a(:)< sample(2)) ), &
                       pack(a(:), a(:)==sample(2))  , &
                qSort( pack(a(:), a(:)> sample(2)) ) ]
        end if
      end function intQsort
      END MODULE intQsortMod
      
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

      MODULE intQueueMod
      implicit none
! Module for QUEUE : First in, First out
! reference : プログラミングコンテスト攻略のための
!              アルゴリズムとデータ構造

      integer(16),parameter :: binSize = 10**6
      integer(16),parameter :: precision = 16
      
      type intQueue
        private
        integer(precision) :: bin( 1:binSize ) = 0
        integer(precision) :: head = 1,   tail = 1
        !head : Where the head value is.
        !tail : Where the blank next to tail is.
        contains
        procedure,public,pass :: initialize => intInit
        procedure,public,pass :: isEmpty    => intIsEmpty
        procedure,public,pass :: isFull     => intIsFull
        procedure,public,pass :: enQueue    => intEnQ
        procedure,public,pass :: deQueue    => intDeQ
      end type
      
      contains
!Reset queue. Not nessesary in first time.
      pure subroutine intInit( q )
        implicit none
        class(intQueue),intent(inout) :: q
        
        q%head = 1
        q%tail = 1
      end subroutine intInit
      
!Check status
      pure function intIsEmpty( q ) result( ans )
        implicit none
        class(intQueue),intent(in) :: q
        logical :: ans
        
        ans = q%head==q%tail
      end function intIsEmpty
      
      
      pure function intIsFull( q ) result( ans )
        implicit none
        class(intQueue),intent(in) :: q
        logical :: ans
        
        ans = q%head==mod( q%tail+1,binSize )
      end function intIsFull

!set x to tail
      subroutine intEnQ( q,x )
        implicit none
        class(intQueue)      ,intent(inout) :: q
        integer(precision),intent(in   ) :: x
        
        if( q%isFull() )then
          print*,'Queue is full,Error!';stop
        else
          q%bin(q%tail) = x
          if( q%tail==binSize )then
            q%tail = 1
          else
            q%tail = q%tail + 1
          end if
        end if
      end subroutine intEnQ
      
!get x from head
      impure function intDeQ( q ) result( x )
        implicit none
        class(intQueue),intent(inout) :: q
        integer(precision) :: x
        
        if( q%isEmpty() )then
          print*,'Stack is empty, Error!';stop
        else
          x = q%bin(q%head)
          if( q%head==binSize )then
            q%head = 1
          else
            q%head = q%head + 1
          end if
        end if
      end function intDeQ
      END MODULE intQueueMod
      
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

      PROGRAM chatInACircle
      use intQsortMod
      use intQueueMod
      IMPLICIT NONE
      INTEGER,PARAMETER :: p = 16
      integer(p) :: n,ans=0
      integer(p),allocatable :: a(:)
      type(intQueue) :: left,right
      integer(p) :: l,r,i
      
      read*,n
      allocate( a(n) )
      read*,a
      
      a = qsort( a )
      a = a(size(a):1:-1)
      
      if( n==2 )then
        print*,a(1)
        stop
      end if
      
      call left%enQueue(a(1))
      call left%enQueue(a(2))
      call right%enQueue(a(2))
      call right%enQueue(a(2))
      ans = ans + a(1)
      
      do i = 3,n
        l = left%deQueue()
        r = right%deQueue()
        
        ans = ans + min(l,r)
        
        call left%enQueue(a(i))
        call right%enQueue(max(l,r))
        call left%enQueue(a(i))
        call right%enQueue(min(l,r))
      end do
      
      print*,ans
      
      stop
      !debugg
      
      print*,n
      print'(*(x,i0))',a
      
      
      END PROGRAM

Measured memory_bytes: 27972