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,parameter,private :: binSize = 10**6
      integer,parameter,private :: p = 16
      
      type intQ
        private
        integer(p),allocatable :: bin(:)
        ! binSizeが大きいとコンパイルに時間かかるのでallocatableにした
        integer(p) :: head = 1,   tail = 1
        !head : 配列の現在の先頭位置
        !tail : 次にpushされた値が入る位置
        
        contains
        procedure,public,pass :: initialize => intQInit
        procedure,public,pass :: isEmpty    => intQisEmpty
        procedure,public,pass :: isFull     => intQisFull
        procedure,public,pass :: push       => intQpush
        procedure,public,pass :: pop        => intQpop
      end type
      
      contains
!キューを初期化、リセットする。初回に必ず呼んでほしい。
      pure elemental subroutine intQinit( q )
        implicit none
        class(intQ),intent(inout) :: q
        
        if( .not.allocated(q%bin) )then
          allocate( q%bin(1:binSize),source=0_p )
        end if
        
        q%head = 1
        q%tail = 1
      end subroutine
      
      pure function intQisEmpty( q ) result( ans )
        implicit none
        class(intQ),intent(in) :: q
        logical :: ans
        
        ans = q%head==q%tail
      end function
      
      pure function intQisFull( q ) result( ans )
        implicit none
        class(intQ),intent(in) :: q
        logical :: ans
        
        ans = q%head==mod( q%tail+1,binSize )
      end function

!キューqの末尾にxを追加
      subroutine intQpush( q,x )
        implicit none
        class(intQ),intent(inout) :: q
        integer(p) ,intent(in   ) :: x
        
        if( q%isFull() )then
          print*,'Queue is full,Error!';stop
        end if
        
        q%bin(q%tail) = x
        q%tail = mod( q%tail+1,binSize )
      end subroutine
      
!キューqの先頭を取り出す。
      impure function intQpop( q ) result( x )
        implicit none
        class(intQ),intent(inout) :: q
        integer(p) :: x
        
        if( q%isEmpty() )then
          print*,'Stack is empty, Error!';stop
        end if
        
        x = q%bin(q%head)
        q%head = mod( q%head+1, binSize )
      end function
      
      END MODULE intQueueMod

!!!!!  procedure list  !!!!!
! type(intQ) :: Q
! Q%push( int )
! int = Q%pop()
! logical = Q%isEmpty()
! logical = Q%isFull()
! Q%initialize()
! 
! initialize()は必ず呼んでね!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

      PROGRAM chatInACircle
      use intQsortMod
      use intQueueMod
      IMPLICIT NONE
      INTEGER,PARAMETER :: p = 16
      integer(p) :: n,ans=0
      integer(p),allocatable :: a(:)
      type(intQ) :: 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%initialize()
      call right%initialize()
      
      call left%push(a(1))
      call left%push(a(2))
      call right%push(a(2))
      call right%push(a(2))
      ans = ans + a(1)
      
      do i = 3,n
        l = left%pop()
        r = right%pop()
        
        ans = ans + min(l,r)
        
        call left%push(a(i))
        call right%push(max(l,r))
        call left%push(a(i))
        call right%push(min(l,r))
      end do
      
      print*,ans
      
      stop
      !debugg
      
      print*,n
      print'(*(x,i0))',a
      
      
      END PROGRAM


Measured memory_bytes: 46692