Version 10.1 doesn't have LongestOrderedSequence. For the sorted case I might therefore use:

Reap[ Fold[If[#2[[2]] > #, #, Sow[#2][[2]]] &, ∞, l] ][[2, 1]] 

{{1, 4}, {2, 4}, {5, 3}, {6, 2}} 

Version 10.1 doesn't have LongestOrderedSequence. For the sorted case I might therefore use:

Reap[ Fold[If[#2[[2]] > #, #, Sow[#2][[2]]] &, ∞, l] ][[2, 1]] 

{{1, 4}, {2, 4}, {5, 3}, {6, 2}} 

Compiled function for better performance:

 Compile[{{a, _Integer, 2}}, Module[{list = Internal`Bag[Rest[{0}], 2]}, Fold[If[#2[[2]] > #, #, Internal`StuffBag[list, #2, 2]; #2[[2]]] &, a[[1, 2]], a]; Internal`BagPart[list, All] ~Partition~ 2 ] ];