module mod_binary_indexed_tree
  implicit none
  type fenwick_tree
    integer :: n
    integer, pointer :: arr(:) => null()
  end type fenwick_tree
  private
  public :: fenwick_tree, init_bit
  public :: add, summate, update, maximum
contains
  subroutine init_bit(bit,n)
    implicit none
    type(fenwick_tree) :: bit
    integer, intent(in) :: n
    bit%n = n
    allocate(bit%arr(n))
    bit%arr = 0
    return
  end subroutine init_bit
  subroutine add(bit,i,v)
    implicit none
    type(fenwick_tree) :: bit
    integer, intent(in) :: i, v
    integer :: x
    x = i
    do while (x <= bit%n)
      bit%arr(x) = bit%arr(x)+v
      x = x+and(x,-x)
    end do
    return
  end subroutine add
  function summate(bit,i) result(s)
    implicit none
    type(fenwick_tree) :: bit
    integer, intent(in) :: i
    integer :: x, s
    x = i
    s = 0
    do while (x > 0)
      s = s+bit%arr(x)
      x = x-and(x,-x)
    end do
    return
  end function summate
  subroutine update(bit,i,v)
    implicit none
    type(fenwick_tree) :: bit
    integer, intent(in) :: i, v
    integer :: x
    x = i
    do while (x <= bit%n)
      if (bit%arr(x) < v) bit%arr(x) = v
      x = x+and(x,-x)
    end do
    return
  end subroutine update
  function maximum(bit,i) result(m)
    implicit none
    type(fenwick_tree) :: bit
    integer, intent(in) :: i
    integer :: x, m
    x = i
    m = 0
    do while (x > 0)
      m = max(m,bit%arr(x))
      x = x-and(x,-x)
    end do
    return
  end function maximum
end module mod_binary_indexed_tree
program sequence_decomposing
  use mod_binary_indexed_tree
  implicit none
  type(fenwick_tree) :: bit
  integer :: n, a(100000) = 0, t, m = 0, i
  read(*,*) n
  do i = 1, n
    read(*,*) a(i)
    a(i) = -a(i)
  end do
  call compress(a(1:n))
  call init_bit(bit,n)
  do i = 1, n
    t = maximum(bit,a(i))+1
    m = max(m,t)
    call update(bit,a(i),t)
  end do
  write(*,'(i0)') m
  stop
contains
  subroutine compress(x)
    implicit none
    integer, intent(inout) :: x(:)
    integer :: y(size(x),2), i, n, k
    n = size(x)
    y(:,1) = x
    do i = 1, n
      y(i,2) = i
    end do
    call quick_sort(y,1)
    k = 0
    x(y(1,2)) = 1
    do i = 2, n
      if (y(i,1) == y(i-1,1)) k = k+1
      x(y(i,2)) = i-k
    end do
    return
  end subroutine compress
  recursive subroutine quick_sort(a,i)
    implicit none
    integer, intent(inout) :: a(:,:)
    integer, intent(in) :: i
    integer :: p, c(size(a(1,:)))
    integer :: n, l, r, m
    n = size(a(:,1))
    l = 1
    r = n
    m = (l+r)/2
    p = a(l,i)+a(m,i)+a(r,i)-max(a(l,i),a(m,i),a(r,i))-min(a(l,i),a(m,i),a(r,i))
    do
      do while (a(l,i) < p)
        l = l+1
      end do
      do while (a(r,i) > p)
        r = r-1
      end do
      if (l >= r) exit
      c = a(l,:)
      a(l,:) = a(r,:)
      a(r,:) = c
      l = l+1
      r = r-1
    end do
    if (l > 2) call quick_sort(a(1:l-1,:),i)
    if (n > r+1) call quick_sort(a(r+1:n,:),i)
    return
  end subroutine quick_sort
end program sequence_decomposing