Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の整数からなる数列 A = \{ A_1, A_2, \cdots, A_N \} が与えられます。 N 個それぞれの整数に対して、色を 1 つ選んでその色を塗ります。 この時、以下の条件を満たす必要があります:
- A_i と A_j (i < j) が同じ色で塗られているならば A_i < A_j が成立する
条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 : A_N
出力
条件を満たすように色を塗る時、用いる色の数の最小値を出力せよ。
入力例 1
5 2 1 4 5 3
出力例 1
2
例えば、2, 3 を赤色、1, 4, 5 を青色で塗れば 2 色で条件を満たす塗り方が出来ます。
入力例 2
4 0 0 0 0
出力例 2
4
全ての整数を異なる色で塗るしかありません。
Score : 500 points
Problem Statement
You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}. For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:
- If A_i and A_j (i < j) are painted with the same color, A_i < A_j.
Find the minimum number of colors required to satisfy the condition.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N A_1 : A_N
Output
Print the minimum number of colors required to satisfy the condition.
Sample Input 1
5 2 1 4 5 3
Sample Output 1
2
We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.
Sample Input 2
4 0 0 0 0
Sample Output 2
4
We have to paint all the integers with distinct colors.