Яхуб недавно освоил сортировку пузырьком, алгоритм, с помощью которого можно отсортировать по возрастанию перестановку, состоящую из n элементов, a₁, a₂, ... a_n. Яхубу этот алгоритм показался очень скучным, поэтому он изобрел свой собственный граф. Этот граф (назовем его G) изначально состоит из n вершин и 0 ребер. При запуске сортировки пузырьком ребра добавляются в граф так, как показано в приведенном ниже алгоритме (псевдокод).

procedure bubbleSortGraph()
    построить граф G с n вершинами и 0 ребрами
    repeat
        swapped = false
        for i = 1 to n - 1 (обе границы включительно) do:
            if a[i] > a[i + 1] then
                добавить неориентированное ребро в G между вершинами a[i] и a[i + 1]
                swap( a[i], a[i + 1] ) /* поменять местами a[i] и a[i + 1] */
                swapped = true
            end if
        end for
    until not swapped 
    /* повторять цикл пока перестановка не станет отсортированной */ 
end procedure

Независимое множество в графе — это такое множество вершин в графе, в котором никакие две вершины не являются смежными (следовательно, между вершинами независимого множества нет ребер). Максимальное независимое множество — это такое независимое множество, у которого наибольшая мощность (размер). Вам дана перестановка, вычислите размер максимального независимого множества графа G, если мы построим его процедурой bubbleSortGraph, передав в качестве перестановки a заданную перестановку.