Recall the longest increasing sub$-$sequence problem we discussed in class, which had an

$O(n^2)$ time solution. Design an $O(nlogn)$ time solution. $[$Hint: you might want to maintain

a balanced binary search tree $($BST$)($e$.$g$.,$ AVL tree$)$ with some extra information.$]$ Find elements, not length.