Largest Increasing Subsequence

Petya is preparing a problem for a local contest in his school. The problem is to find a longest increasing subsequence in a given permutation. A *permutation* of size $n$ is a sequence of $n$ numbers $a_1, \ldots, a_n$ such that every number from $1$ to $n$ occurs in the sequence exactly once. An *increasing subsequence* of length $k$ of the sequence $a_1, \ldots, a_n$ is a sequence of indices $i