Minimum Stacks for Permutation Sorting

You are given a permutation with \(n\) numbers, \(a_1,a_2,\dots,a_n\) (\(1\le a_i\le n\) and \(a_i\neq a_j\) when \(i\neq j\)).

You want to sort these numbers using \(m\) stacks. The process is as follows:

1. Initially, all \(m\) stacks are empty.
2. You push each number into one of the stacks in the order given by the permutation \(a_1,a_2,\dots,a_n\). When you push a number onto a stack, it is placed on top of that stack. Note that within each stack, the numbers must be arranged so that when the stack is popped, the elements pop out in ascending order. Since each stack is LIFO (last-in-first-out), the sequence of numbers pushed into each stack must be strictly decreasing.
3. After pushing all numbers, you will pop all the elements. However, if you start popping from a stack \(S\), you must pop all elements from \(S\) before you can pop from any other stack. You can choose the order in which to empty the stacks, but the overall popped sequence must be \(1,2,\dots,n\).

It can be shown that the minimum number \(m\) of stacks required is equal to the length of the longest increasing subsequence of the permutation. Your task is to determine this minimum number \(m\).

inputFormat

The first line contains a single integer \(n\), the number of elements in the permutation.

The second line contains \(n\) distinct integers \(a_1,a_2,\dots,a_n\) representing the permutation.

outputFormat

Output a single integer representing the minimum number of stacks needed.

sample

5
3 2 1 5 4

2