Longest increasing sequence in nlogn.To find longest decreasing subseq just negate the input array and find the longest increasing sub.