Рудольф очень любит классические алгоритмические задачи. В том числе задачу о наибольшей возрастающей подпоследовательности.
Наибольшая возрастающая подпоследовательность (НВП) массива $$$A$$$ длины $$$N$$$ — это последовательность $$$A[i_1] \lt A[i_2] \lt ... \lt A[i_k]$$$ элементов массива $$$A$$$ таких, что $$$i_1 \lt i_2 \lt ... \lt i_k$$$, $$$0 \le i_j \lt N$$$, причём $$$k$$$ — наибольшее из возможных.
Обычно данную задачу решают для массива целых чисел. Однако это слишком скучно. Рудольф подготовил массив пар целых чисел, причём одна пара больше другой, только если одновременно и первый, и второй элемент пары больше соответствующих элементов другой пары.
Чтобы вам было веселее, введём ещё одно условие — перед поиском НВП порядок пар в массиве можно изменить. Очевидно, что Рудольф будет менять порядок пар так, чтобы максимизировать НВП.
Первая строка входных данных содержит целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — количество элементов в массиве.
Следующие $$$N$$$ строк содержат элементы массива. Каждая строка содержит целые числа $$$F_i$$$ и $$$S_i$$$ ($$$1 \le F_i, S_i \le 10^9$$$) — первый и второй элемент $$$i$$$-й пары соответственно.
Выведите одно целое число — длину наибольшей возрастающей подпоследовательности.
5 1 5 5 1 2 2 3 3 4 1
2
10 7 9 10 1 3 2 7 8 4 5 4 8 7 7 1 3 5 17 1 3
3
