program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int64):: n,i,j
    integer(int64), allocatable:: a(:), dp(:,:)
    integer(int64),parameter:: nmin=-1000000000

    read*, n
    allocate(a(n), dp(0:n,-1:n))
    read*, a(:)
    dp(:,:) = nmin
    dp(:,-1:0) = 0

    do i=1,n
        do j=1,(i+1)/2
            dp(j,i) = max(dp(j,i-1),dp(j-1,i-2)+a(i))
        end do
    end do

    print*, dp(n/2,n)
end program name