module heap_mod
    use,intrinsic :: iso_fortran_env
    type heap
        integer(int32):: i
        integer(int32), allocatable:: key(:)
        integer(int32), allocatable:: val(:)
    contains
        procedure:: append => append_heap
        procedure:: pop => pop_heap
        procedure:: top_key => top_key
        procedure:: top_val => top_val
        procedure:: size => size_heap
    end type
    interface heap
        module procedure init_heap
    end interface
    private
    public:: heap
contains
    function init_heap() result(h)
        type(heap):: h
        h%i=0
        allocate(h%key(1))
        allocate(h%val(1))
    end function

    function size_heap(h) result(ret)
        class(heap):: h
        integer(int32):: ret
        ret = h%i
    end function

    function top_key(h) result(ret)
        class(heap):: h
        integer(int32):: ret
        if (h%i <= 0) then
            print'(a)', 'heap is empty!'
            stop
        end if
        ret = h%key(1)
    end function

    function top_val(h) result(ret)
        class(heap):: h
        integer(int32):: ret
        if (h%i <= 0) then
            print'(a)', 'heap is empty!'
            stop
        end if
        ret = h%val(1)
    end function

    subroutine append_heap(h,k,v)
        class(heap):: h
        integer(int32):: k,v
        if (h%i+1 >= size(h%key)) call add(h)
        ! print*, 'a'
        h%i=h%i+1
        h%key(h%i) = k
        h%val(h%i) = v
        call heap_up(h,h%i)
    end subroutine

    subroutine pop_heap(h,k,v)
        class(heap):: h
        integer(int32),intent(out):: k,v
        k=h%key(1)
        v=h%val(1)
        h%key(1) = h%key(h%i)
        h%val(1) = h%val(h%i)
        h%i=h%i-1
        call heap_down(h,1)
    end subroutine

    subroutine add(h)
        class(heap):: h
        call add_array(h%key)
        call add_array(h%val)
    end subroutine

    subroutine add_array(x)
        integer(int32):: l
        integer(int32), allocatable:: tmp(:),x(:)
        l = size(x(:))
        allocate(tmp(l))
        tmp(:) = x(:)
        deallocate(x)
        allocate(x(l*2))
        x(1:l) = tmp(:)
        deallocate(tmp)
    end subroutine

    recursive subroutine heap_up(h,self)
        class(heap):: h
        integer(int32):: self
        if (self == 1) return

        if (h%key(self) > h%key(self/2))then
            call swap(h%key(self),h%key(self/2))
            call swap(h%val(self),h%val(self/2))
            call heap_up(h,self/2)
        end if
    end subroutine

    recursive subroutine heap_down(h,self)
        class(heap):: h
        integer(int32):: self,c1,c2

        c1 = self*2
        c2 = c1+1
        if (c2 <= h%i) then
            if (h%key(c1) >= h%key(c2)) then
                if (h%key(c1) > h%key(self)) then
                    call swap(h%key(c1),h%key(self))
                    call swap(h%val(c1),h%val(self))
                    call heap_down(h,c1)
                end if
            else
                if (h%key(c2) > h%key(self)) then
                    call swap(h%key(c2),h%key(self))
                    call swap(h%val(c2),h%val(self))
                    call heap_down(h,c2)
                end if
            end if
        else if (c1 <= h%i) then
            if (h%key(c1) >= h%key(self)) then
                call swap(h%key(c1),h%key(self))
                call swap(h%val(c1),h%val(self))
                call heap_down(h,c1)
            end if
        else
            return
        end if
    end subroutine

    subroutine swap(x,y)
        integer(int32):: x,y,t
        t=x; x=y; y=t
    end subroutine
end module

program main
    use,intrinsic :: iso_fortran_env
    use heap_mod
    implicit none
    integer(int32):: k,t,i,prev_cake, ans
    integer(int32):: ncake, nnum, nextcake, nextnum
    integer(int32), allocatable:: a(:)
    type(heap):: cakes

    read*, k,t
    allocate(a(t))
    read*, a(:)
    cakes = heap()
    do i=1,t
        ! print*, 'a'
        call cakes%append(a(i),i)
    end do

    prev_cake = -1
    ans=0

    do while(cakes%top_key() > 0)
        call cakes%pop(nnum, ncake)
        if (ncake /= prev_cake) then
            call cakes%append(nnum-1,ncake)
            prev_cake = ncake
        else
            if (cakes%size() > 0) then
                if (cakes%top_key() > 0) then
                    call cakes%pop(nextnum, nextcake)
                    call cakes%append(nnum,ncake)
                    call cakes%append(nextnum-1,nextcake)
                    prev_cake = nextcake
                else
                    call cakes%append(nnum-1,ncake)
                    ans=ans+1
                    prev_cake = ncake
                end if
            else 
                call cakes%append(nnum-1,ncake)
                ans=ans+1
                prev_cake = ncake
            end if
        end if
    end do
    print'(i0)', ans
end program main
    

Measured memory_bytes: 256