program sample
    implicit none
    real(8)::a
    integer(8) :: b,c,i,j,m,n,k,a1,b1,c1
    integer(8), allocatable  ::x(:) 

    read(*,*) n
  
    allocate(x(n))
    read(*,*) x
    
    call msort(x)
    a=real(x(1))/2**(n-1)
    write(*,*)a
    do i=2,n
       a=a+real(x(i))/2**(n+1-i) 
    end do
    write(*,*)a
    deallocate(x)

    stop

    contains

    recursive subroutine msort(x)
    implicit none
    integer(8), intent(inout) :: x(:)
 
    integer(8) :: n, mid, i, j, k
    integer(8), allocatable :: tmp(:)
    
    n = size(x)
    
    if(n == 1) then
      return
    end if
 
    !
    ! 前半と後半に分けてソート
    ! 1~midとmid+1~nをそれぞれソート済みにする
    !
    mid = n / 2
    call msort(x(:mid))
    call msort(x(mid+1:))
 
    !
    ! tmpという配列にxを一時的に保管
    ! マージソートは外部ソート
    !
    allocate(tmp(n))
    tmp = x
 
    ! tmpの後半部分を左右反転
    do k = n, mid+1, -1
      tmp(k) = x(mid + n - k + 1)
    end do
 
    ! iは前半のリストのうちまだ見ていないものの最小値
    ! jは後半のリストのうちまだ見ていないものの最小値
    ! kは見た回数の合計
    i = 1
    j = n
 
    do k = 1, n
      !
      ! 一番左と一番右のうち小さい方をxに入れていく
      ! ここが等号つき不等号なので、安定ソートとなる
      !
      if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
      else
        x(k) = tmp(j)
        j = j - 1
      end if
    end do
    
    deallocate(tmp)
    return
  end subroutine msort
end program sample
  

