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.

Examples

Input

5
2
1
4
5
3


Output

2


Input

4
0
0
0
0


Output

4

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            long current = scanner.nextLong();
            a[i] = current;
        }

        List<Long> numbers = new ArrayList<>();
        for (long num : a) {
            int value = Collections.binarySearch(
                    numbers, num
            );
            if (value >= 0 && value < numbers.size()) {
                int lessValue = Collections.binarySearch(
                        numbers, num - 1
                );
                if (lessValue >= 0 && lessValue < numbers.size()) {
                    numbers.set(lessValue, num);
                } else {
                    int lessPos = -1 * (lessValue + 1);
                    if (lessPos - 1 >= 0 && numbers.get(lessPos - 1) < num) {
                        numbers.set(lessPos - 1, num);
                    } else {
                        numbers.add(value, num);
                    }
                }
                continue;
            }

            int pos = -1 * (value + 1);
            if (pos - 1 >= 0 && numbers.get(pos - 1) < num) {
                numbers.set(pos - 1, num);
            } else {
                numbers.add(pos, num);
            }


        }
        System.out.println(numbers.size());

    }
}
