program lexicographic_constraints
  implicit none
  integer(8)              :: n, m, i, j, k
  integer(8), allocatable :: a(:), s(:)
  read(*,*) n
  allocate(a(n))
  read(*,*) a(:)
  m = maxval(a)+1
  allocate(s(m))
  s = 0
  k = 1
  if (n .gt. 1) then
     loop: do i = 2, n
        if (a(i) .gt. a(i-1)) cycle
        s(a(i)+1:a(i-1)+1) = 0
        s(a(i)) = s(a(i)) + 1
        if (s(a(i)) .gt. k-1) then
           if (a(i) .gt. 1) then
              do j = a(i)-1, 1, -1
                 if (s(j) .lt. k-1) then
                    s(j) = s(j) + 1
                    s(j+1:a(i)) = 0
                    cycle loop
                 end if
              end do
           end if
           k = k + 1
        end if
     end do loop
  end if
  deallocate(a,s)
  write(*,'(i0)') k
  stop
end program lexicographic_constraints