Longest Increasing Path of Palaces

You are given a list of palaces, each represented by a pair of integers \(x\) and \(y\), which denote its coordinates. A valid path is defined as a sequence of palaces such that when the list is sorted by the \(x\)-coordinate, the corresponding \(y\)-coordinates form a strictly increasing sequence. In other words, if the palaces in the path are \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\) (with \(x_1 \le x_2 \le \dots \le x_k\)), then it must hold that \(y_1 < y_2 < \dots < y_k\).

This problem essentially reduces to finding the Longest Increasing Subsequence (LIS) in the sequence of \(y\)-coordinates after sorting the palaces by their \(x\)-coordinates.

For example, given the palaces [(1, 2), (2, 3), (3, 4), (2, 2), (3, 5)], one optimal sequence is [(1, 2), (2, 3), (3, 4), (3, 5)] which has a length of 4.

inputFormat

The input is given via stdin as follows:

1. The first line contains an integer \(n\), the number of palaces.
2. The next \(n\) lines each contain two integers \(x\) and \(y\), representing the coordinates of a palace.

outputFormat

Output a single integer to stdout representing the length of the longest increasing sequence (as defined above) of palaces.

5
1 2
2 3
3 4
2 2
3 5

4