program prob5
    implicit none
    integer(16)::i,j,k,X,M, mid1, mid2
    integer(16), allocatable::a(:), b(:)
    read(*,*) M
    allocate(a(M), b(M))
    read(*,*) a

    b = a

    call heapsort(M,a)

    mid1 = a(M/2)
    mid2 = a(M/2 + 1)

    do i = 1, M
        if(b(i) <= mid1) then
            write(*,*) mid2
        else
            write(*,*) mid1
        end if
    end do

    deallocate(a, b)
    stop
    contains
    subroutine heapsort(n,array)
        implicit none
        integer(16),intent(in) :: n
        integer(16),intent(inout) :: array(1:n)
       
        integer ::i,k,j,l
        double precision :: t
       
        if(n.le.0)then
           write(6,*)"Error, at heapsort"; stop
        endif
        if(n.eq.1)return
      
        l=n/2+1
        k=n
        do while(k.ne.1)
           if(l.gt.1)then
              l=l-1
              t=array(L)
           else
              t=array(k)
              array(k)=array(1)
              k=k-1
              if(k.eq.1) then
                 array(1)=t
                 exit
              endif
           endif
           i=l
           j=l+l
           do while(j.le.k)
              if(j.lt.k)then
                 if(array(j).lt.array(j+1))j=j+1
              endif
              if (t.lt.array(j))then
                 array(i)=array(j)
                 i=j
                 j=j+j
              else
                 j=k+1
              endif
           enddo
           array(i)=t
        enddo
      
        return
    end subroutine heapsort
end program prob5