module mod_linked_list
implicit none
type t_node
private
integer :: item
type(t_node), pointer :: prev => null()
type(t_node), pointer :: next => null()
end type t_node
type t_linked_list
private
integer :: num = 0
type(t_node), pointer :: head => null()
type(t_node), pointer :: tail => null()
contains
procedure :: add_first => add_first
procedure :: add_last => add_last
procedure :: poll_first => poll_first
procedure :: poll_last => poll_last
procedure :: peek_first => peek_first
procedure :: peek_last => peek_last
procedure :: clear => clear
procedure :: get => get
procedure :: remove => remove
procedure :: replace => replace
procedure :: first_index_of => first_index_of
procedure :: last_index_of => last_index_of
procedure :: size => size_of
end type t_linked_list
contains
function new_node(item) result(node)
integer, intent(in) :: item
type(t_node), pointer :: node
allocate(node)
node%item = item
end
subroutine add_first(this,item)
class(t_linked_list), intent(inout) :: this
integer, intent(in) :: item
type(t_node), pointer :: node
node => new_node(item)
if (associated(this%tail)) then
node%next => this%head
this%head%prev => node
else
this%tail => node
end if
this%head => node
this%num = this%num+1
end
subroutine add_last(this,item)
class(t_linked_list), intent(inout) :: this
integer, intent(in) :: item
type(t_node), pointer :: node
node => new_node(item)
if (associated(this%head)) then
node%prev => this%tail
this%tail%next => node
else
this%head => node
end if
this%tail => node
this%num = this%num+1
end
function poll_first(this) result(item)
class(t_linked_list), intent(inout) :: this
integer :: item
type(t_node), pointer :: node
item = this%head%item
node => this%head%next
deallocate(this%head)
this%head => node
if (associated(node)) then
node%prev => null()
else
this%tail => null()
end if
this%num = this%num-1
end
function poll_last(this) result(item)
class(t_linked_list), intent(inout) :: this
integer :: item
type(t_node), pointer :: node
item = this%tail%item
node => this%tail%prev
deallocate(this%tail)
this%tail => node
if (associated(node)) then
node%next => null()
else
this%head => null()
end if
this%num = this%num-1
end
function peek_first(this) result(item)
class(t_linked_list), intent(in) :: this
integer :: item
item = this%head%item
end
function peek_last(this) result(item)
class(t_linked_list), intent(in) :: this
integer :: item
item = this%tail%item
end
subroutine clear(this)
class(t_linked_list), intent(inout) :: this
type(t_node), pointer :: node, next
if (.not.associated(this%head)) return
node => this%head
do while (associated(node%next))
next => node%next
deallocate(node)
node => next
end do
this%head => null()
this%tail => null()
this%num = 0
end
function get(this,i) result(item)
class(t_linked_list), intent(in) :: this
integer, intent(in) :: i
integer :: item, idx
type(t_node), pointer :: node
if (i <= (this%num+1)/2) then
idx = 1
node => this%head
do while (idx < i)
node => node%next
idx = idx+1
end do
else
idx = this%num
node => this%tail
do while (idx > i)
node => node%prev
idx = idx-1
end do
end if
item = node%item
end
function remove(this,i) result(item)
class(t_linked_list), intent(inout) :: this
integer, intent(in) :: i
integer :: item, idx
type(t_node), pointer :: node
if (i == 1) then
item = poll_first(this)
return
end if
if (i == this%num) then
item = poll_last(this)
return
end if
if (i <= (this%num+1)/2) then
idx = 1
node => this%head
do while (idx < i)
node => node%next
idx = idx+1
end do
else
idx = this%num
node => this%tail
do while (idx > i)
node => node%prev
idx = idx-1
end do
end if
item = node%item
node%prev%next => node%next
node%next%prev => node%prev
deallocate(node)
this%num = this%num-1
end
subroutine replace(this,i,item)
class(t_linked_list), intent(inout) :: this
integer, intent(in) :: i, item
integer :: idx
type(t_node), pointer :: node
if (i <= (this%num+1)/2) then
idx = 1
node => this%head
do while (idx < i)
node => node%next
idx = idx+1
end do
else
idx = this%num
node => this%tail
do while (idx > i)
node => node%prev
idx = idx-1
end do
end if
node%item = item
end
subroutine show_all(this)
type(t_linked_list), intent(in) :: this
type(t_node), pointer :: node, next
if (.not.associated(this%head)) return
node => this%head
write(*,'(i0)',advance='no') node%item
do while (associated(node%next))
node => node%next
write(*,'(x,i0)',advance='no') node%item
end do
write(*,*)
end
function first_index_of(this,item) result(idx)
class(t_linked_list), intent(in) :: this
integer, intent(in) :: item
integer :: idx
type(t_node), pointer :: node
idx = 1
node => this%head
do while (associated(node))
if (node%item == item) return
node => node%next
idx = idx+1
end do
idx = -1
end
function last_index_of(this,item) result(idx)
class(t_linked_list), intent(in) :: this
integer, intent(in) :: item
integer :: idx
type(t_node), pointer :: node
idx = this%num
node => this%tail
do while (associated(node))
if (node%item == item) return
node => node%prev
idx = idx-1
end do
idx = -1
end
integer function size_of(this)
class(t_linked_list), intent(in) :: this
size_of = this%num
end
end module mod_linked_list
program tokaido
use mod_linked_list
implicit none
integer :: n, m, a(200000) = 0, x, s = 0, d, i, j
integer :: dp(0:1000000) = 0, tmp
type(t_linked_list) :: deque, tmp1, tmp2
read(*,*) n
read(*,*) a(1:n-1)
if (n > 3) s = sum(a(3:n-1))
d = a(1)-a(2)
do i = 0, s-1
call deque%add_last(i)
end do
do i = 3, n-1
do j = 0, a(i)
call tmp1%add_last(deque%peek_first())
call tmp2%add_last(deque%poll_first())
end do
do j = 0, a(i)
call deque%add_first(tmp1%poll_last())
end do
tmp = tmp2%poll_first()
do j = 1, a(i)
call deque%add_first(tmp2%poll_first())
tmp = deque%poll_last()
end do
end do
do i = 0, s-1
dp(i) = deque%poll_first()
end do
read(*,*) m
do i = 1, m
read(*,*) x
if (x >= s) then
write(*,'(i0)') x-s+d
cycle
end if
write(*,'(i0)') dp(x)+d
end do
end program tokaido