Chef and Points

Today, you finally have a chance to compete with a famous coder like Chef and prove your mettle. Chef has $n$ distinct points in 2-D plane, i.e. there are never two points with both $x$ and $y$ coordinate equal and there are no two points with the same $x$ coordinate. Consider a subset of the above $n$ points which can be arranged as a sequence $p_1, \dots, p_k$, such that $x_{p_1} < x_{p_2} < \d