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:4))
    read*, a(:)
    dp(:,:) = nmin
    dp(0,:) = 0

    do i=1,n
        do j=max(1,(i-1)/2-1),(i+1)/2
            dp(j,mod(i-1,4)+1) = max(dp(j,mod(i-2,4)+1),dp(j-1,mod(i-3,4)+1)+a(i))
        end do
    end do
    print*, dp((n)/2,mod(n-1,4)+1)
end program name