Рудольф очень любит классические алгоритмические задачи. В том числе задачу о наибольшей возрастающей подпоследовательности.

Наибольшая возрастающая подпоследовательность (НВП) массива $$$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$$$ — наибольшее из возможных.

Обычно данную задачу решают для массива целых чисел. Однако это слишком скучно. Рудольф подготовил массив пар целых чисел, причём одна пара больше другой, только если одновременно и первый, и второй элемент пары больше соответствующих элементов другой пары.

Чтобы вам было веселее, введём ещё одно условие — перед поиском НВП порядок пар в массиве можно изменить. Очевидно, что Рудольф будет менять порядок пар так, чтобы максимизировать НВП.