module mod_bitset
  implicit none
  type bitset
    integer :: k
    integer(8), pointer :: bits(:)
  end type bitset
  private
  public :: bitset, init_bitset, set, get, shift_right, shift_left
  public :: shift_or, or_with, and_with
contains
  subroutine init_bitset(bs,n)
    implicit none
    type(bitset), intent(inout) :: bs
    integer, intent(in) :: n
    integer :: k
    k = (n+63)/64
    bs%k = k
    allocate(bs%bits(0:k))
    bs%bits = 0_8
    return
  end subroutine init_bitset
  subroutine set(bs,idx,bit)
    implicit none
    type(bitset), intent(in) :: bs
    integer, intent(in) :: idx
    logical, intent(in) :: bit
    integer :: i, k
    i = idx/64
    k = mod(idx,64)
    if (bit) then
      bs%bits(i) = or(bs%bits(i),ishft(1_8,k))
    else
      bs%bits(i) = and(bs%bits(i),not(ishft(1_8,k)))
    end if
    return
  end subroutine set
  function get(bs,idx) result(bit)
    implicit none
    type(bitset), intent(in) :: bs
    integer, intent(in) :: idx
    logical :: bit
    integer :: i, k
    i = idx/64
    k = mod(idx,64)
    bit = and(bs%bits(i),ishft(1_8,k)).ne.0_8
    return
  end function get
  subroutine shift_right(bs,n)
    implicit none
    type(bitset), intent(in) :: bs
    integer, intent(in) :: n
    integer :: i, k, x, s
    i = n/64
    k = mod(n,64)
    do x = 0, bs%k
      s = x+i
      if (s.gt.bs%k) then
        bs%bits(x) = 0_8
      end if
      bs%bits(x) = ishft(bs%bits(s),-k)
      if (k.gt.0.and.s+1.le.bs%k) then
        bs%bits(x) = or(bs%bits(x),ishft(bs%bits(s+1),64-k))
      end if
    end do
    return
  end subroutine shift_right
  subroutine shift_left(bs,n)
    implicit none
    type(bitset), intent(in) :: bs
    integer, intent(in) :: n
    integer :: i, k, x, s
    i = n/64
    k = mod(n,64)
    do x = bs%k, 0, -1
      s = x-i
      if (s.lt.0) then
        bs%bits(x) = 0_8
      end if
      bs%bits(x) = ishft(bs%bits(s),k)
      if (k.gt.0.and.s.gt.0) then
        bs%bits(x) = or(bs%bits(x),ishft(bs%bits(s-1),-(64-k)))
      end if
    end do
    return
  end subroutine shift_left
  subroutine shift_or(bs,n)
    implicit none
    type(bitset), intent(in) :: bs
    integer, intent(in) :: n
    integer :: i, k, x, s
    i = n/64
    k = mod(n,64)
    do x = bs%k, i+1, -1
      s = x-i
      bs%bits(x) = ishft(bs%bits(s),k)
      if (k.gt.0) then
        bs%bits(x) = or(bs%bits(x),ishft(bs%bits(s-1),-(64-k)))
      end if
    end do
    bs%bits(i) = or(bs%bits(i),ishft(bs%bits(0),k))
    return
  end subroutine shift_or
  subroutine or_with(bs1,bs2)
    implicit none
    type(bitset), intent(in) :: bs1, bs2
    integer :: i
    do i = 0, bs1%k
      bs1%bits(i) = or(bs1%bits(i),bs2%bits(i))
    end do
    return
  end subroutine or_with
  subroutine and_with(bs1,bs2)
    implicit none
    type(bitset), intent(in) :: bs1, bs2
    integer :: i
    do i = 0, bs1%k
      bs1%bits(i) = and(bs1%bits(i),bs2%bits(i))
    end do
    return
  end subroutine and_with
end module mod_bitset
program median_sum
  use mod_bitset
  implicit none
  type(bitset) :: bs
  integer :: n, a(2000), s, i
  a = 0
  read(*,*) n
  read(*,*) a(1:n)
  call init_bitset(bs,2000*n)
  do i = 1, n
    call shift_or(bs,a(i))
    call set(bs,a(i),.true.)
  end do
  s = sum(a(1:n))
  do i = (s+1)/2, 2000*n
    if (get(bs,i)) then
      write(*,'(i0)') i
      stop
    end if
  end do
  stop
end program median_sum