module mod_tree_map
  implicit none
  type t_entry
    private
    integer :: key
    integer :: val
  end type
  type t_node
    private
    type(t_node), pointer :: left => null(), right => null()
    integer :: level = 1
    type(t_entry), pointer :: e => null()
  end type
  type t_tree_map
    private
    type(t_node), pointer :: root => null()
    integer :: deflt = 0
  contains
    procedure :: size => size_of
    procedure :: clear => clear
    procedure :: set_default => set_default
    procedure :: put => put
    procedure :: remove => remove
    procedure :: get => get
    procedure :: contain => contain
    procedure :: first_key => get_first_key
    procedure :: last_key => get_last_key
    procedure :: floor_key => floor_key
    procedure :: lower_key => lower_key
    procedure :: ceiling_key => ceiling_key
    procedure :: higher_key => higher_key
    procedure :: get_keys => get_keys
  end type
contains
  function new_entry(key,val) result(e)
    integer, intent(in) :: key
    integer, intent(in) :: val
    type(t_entry), pointer :: e
    e => null()
    allocate(e)
    e%key = key
    e%val = val
  end
  function new_node(e) result(n)
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    n => null()
    allocate(n)
    n%e => e
  end
  integer function level(n)
    type(t_node), pointer, intent(in) :: n
    level = 0
    if (.not.associated(n)) return
    level = n%level
  end
  logical function is_leaf(n)
    type(t_node), pointer, intent(in) :: n
    is_leaf = associated(n) .and. .not.associated(n%left) .and. &
    &         .not.associated(n%right)
  end
  recursive function tree_size(n) result(s)
    type(t_node), pointer, intent(in) :: n
    integer :: s
    s = 0
    if (.not.associated(n)) return
    s = 1+tree_size(n%left)+tree_size(n%right)
  end
  function skew(n) result(l)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: l
    l => n
    if (.not.(associated(n) .and. associated(n%left) .and. &
    &   n%left%level == n%level)) return
    l => n%left
    n%left => l%right
    l%right => n
  end
  function split(n) result(r)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: r
    r => n
    if (.not.(associated(n) .and. associated(n%right) .and. &
    &   associated(n%right%right) .and. n%right%right%level == n%level)) return
    r => n%right
    n%right => r%left
    r%left => n
    r%level = r%level+1
  end
  function predecessor(n) result(p)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: p
    p => null()
    if (.not.associated(n%left)) return
    p => n%left
    do while (associated(p%right))
      p => p%right
    end do
  end
  function successor(n) result(s)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: s
    s => null()
    if (.not.associated(n%right)) return
    s => n%right
    do while (associated(s%left))
      s => s%left
    end do
  end
  recursive function insert(n,e) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: t
    t => new_node(e)
    if (.not.associated(n)) return
    t => n
    if (e%key < t%e%key) then
      t%left => insert(t%left,e)
    else if (e%key > t%e%key) then
      t%right => insert(t%right,e)
    else
      t%e => e
    end if
    t => skew(t)
    t => split(t)
  end
  recursive function delete(n,e) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: t, l
    t => n
    if (.not.associated(n)) return
    if (e%key < t%e%key) then
      t%left => delete(t%left,e)
    else if (e%key > t%e%key) then
      t%right => delete(t%right,e)
    else
      if (is_leaf(t)) then
        t => null()
        return
      end if
      if (.not.associated(t%left)) then
        l => successor(t)
        t%right => delete(t%right,l%e)
        t%e => l%e
      else
        l => predecessor(t)
        t%left => delete(t%left,l%e)
        t%e => l%e
      end if
    end if
    t => decrease_level(t)
    t => skew(t)
    t%right => skew(t%right)
    if (associated(t%right)) t%right%right => skew(t%right%right)
    t => split(t)
    t%right => split(t%right)
  end
  function decrease_level(n) result(t)
    type(t_node), pointer, intent(in) :: n
    type(t_node), pointer :: t
    integer :: should_be
    t => n
    should_be = min(level(t%left),level(t%right))+1
    if (t%level > should_be) then
      t%level = should_be
      if (level(t%right) > should_be) t%right%level = should_be
    end if
  end
  recursive subroutine release_tree(t)
    type(t_node), pointer, intent(inout) :: t
    if (.not.associated(t)) return
    call release_tree(t%left)
    call release_tree(t%right)
    deallocate(t)
  end
  recursive subroutine get_keys_list(t,keys,num)
    type(t_node), pointer, intent(in) :: t
    integer, intent(inout) :: keys(:)
    integer, intent(inout) :: num
    if (.not.associated(t)) return
    call get_keys_list(t%left,keys,num)
    num = num+1
    keys(num) = t%e%key
    call get_keys_list(t%right,keys,num)
  end
  integer function size_of(this)
    class(t_tree_map), intent(in) :: this
    size_of = tree_size(this%root)
  end
  subroutine clear(this)
    class(t_tree_map), intent(inout) :: this
    call release_tree(this%root)
    this%root => null()
  end
  subroutine set_default(this,deflt)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: deflt
    this%deflt = deflt
  end
  subroutine put_entry(this,e)
    type(t_tree_map), intent(inout) :: this
    type(t_entry), pointer, intent(in) :: e
    this%root => insert(this%root,e)
  end
  subroutine remove_entry(this,e)
    type(t_tree_map), intent(inout) :: this
    type(t_entry), pointer, intent(in) :: e
    this%root => delete(this%root,e)
  end
  function get_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function contain_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    logical :: ret
    ret = .false.
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret = .true.
        return
      end if
    end do
  end
  function get_first_entry(this) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%left))
      n => n%left
    end do
    ret => n%e
  end
  function poll_first_entry(this) result(ret)
    type(t_tree_map), intent(inout) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%left))
      n => n%left
    end do
    ret => n%e
    this%root => delete(this%root,ret)
  end
  function get_last_entry(this) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%right))
      n => n%right
    end do
    ret => n%e
  end
  function poll_last_entry(this) result(ret)
    type(t_tree_map), intent(inout) :: this
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    if (.not.associated(n)) return
    do while (associated(n%right))
      n => n%right
    end do
    ret => n%e
    this%root => delete(this%root,ret)
  end
  function floor_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        n => n%left
      else if (e%key > n%e%key) then
        if (.not.associated(ret)) then
          ret => n%e
          cycle
        end if
        if (e%key-ret%key > e%key-n%e%key) ret => n%e
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function lower_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_entry), pointer :: ret
    ret => floor_entry(this,new_entry(e%key-1,0))
  end
  function ceiling_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_node), pointer :: n
    type(t_entry), pointer :: ret
    ret => null()
    n => this%root
    do while (associated(n))
      if (e%key < n%e%key) then
        if (.not.associated(ret)) then
          ret => n%e
          cycle
        end if
        if (e%key-ret%key < e%key-n%e%key) ret => n%e
        n => n%left
      else if (e%key > n%e%key) then
        n => n%right
      else
        ret => n%e
        return
      end if
    end do
  end
  function higher_entry(this,e) result(ret)
    type(t_tree_map), intent(in) :: this
    type(t_entry), pointer, intent(in) :: e
    type(t_entry), pointer :: ret
    ret => ceiling_entry(this,new_entry(e%key+1,0))
  end
  subroutine get_keys(this,keys,num)
    class(t_tree_map), intent(in) :: this
    integer, intent(inout) :: keys(:)
    integer, intent(inout) :: num
    keys = 0
    num = 0
    call get_keys_list(this%root,keys,num)
  end
  subroutine put(this,key,val)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: key
    integer, intent(in) :: val
    call put_entry(this,new_entry(key,val))
  end
  subroutine remove(this,key)
    class(t_tree_map), intent(inout) :: this
    integer, intent(in) :: key
    call remove_entry(this,new_entry(key,0))
  end
  function get(this,key) result(val)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: val
    val = this%deflt
    tmp => get_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    val = tmp%val
  end
  logical function contain(this,key)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    contain = contain_entry(this,new_entry(key,0))
  end
  function get_first_key(this) result(key)
    class(t_tree_map), intent(in) :: this
    type(t_entry), pointer :: tmp
    integer :: key
    key = this%deflt
    tmp => get_first_entry(this)
    if (.not.associated(tmp)) return
    key = tmp%key
  end
  function get_last_key(this) result(key)
    class(t_tree_map), intent(in) :: this
    type(t_entry), pointer :: tmp
    integer :: key
    key = this%deflt
    tmp => get_last_entry(this)
    if (.not.associated(tmp)) return
    key = tmp%key
  end
  function floor_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => floor_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function lower_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => lower_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function ceiling_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => ceiling_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
  function higher_key(this,key) result(ret)
    class(t_tree_map), intent(in) :: this
    integer, intent(in) :: key
    type(t_entry), pointer :: tmp
    integer :: ret
    ret = this%deflt
    tmp => higher_entry(this,new_entry(key,0))
    if (.not.associated(tmp)) return
    ret = tmp%key
  end
end module mod_tree_map
program lexicographic_constraints
  implicit none
  integer :: n, a(200000) = 0, l = 0, r, m
  read(*,*) n
  read(*,*) a(1:n)
  r = n
  do while (r-l > 1)
    m = (l+r)/2
    if (check(m)) then
      r = m
    else
      l = m
    end if
  end do
  write(*,'(i0)') r
contains
  logical function check(m)
    use mod_tree_map
    type(t_tree_map) :: map
    type(t_entry), pointer :: tmp
    integer, intent(in) :: m
    integer :: i, j, x
    call map%clear()
    check = .false.
    do i = 1, n
      if (a(i) > a(i-1)) cycle
      if (m == 1) return
      do while (map%size() > 0 .and. map%last_key() > a(i))
        tmp => poll_last_entry(map)
      end do
      j = a(i)
      do
        x = map%get(j)+1
        if (x >= m) then
          call map%remove(j)
          j = j-1
          if (j == 0) return
        else
          call map%put(j,x)
          exit
        end if
      end do
    end do
    check = .true.
  end
end program lexicographic_constraints

Measured memory_bytes: 914944