Longest Increasing Message Sequence

In a messaging system, each message is associated with a unique identifier and a timestamp indicating when it was sent. After sorting the messages by their timestamps in ascending order, your task is to determine the length of the longest subsequence of messages in which the message identifiers are in strictly increasing order.

Formally, given a sequence of messages, let each message be represented by a tuple ( (m_i, t_i) ) where ( m_i ) is the message ID and ( t_i ) is the timestamp. After sorting the messages such that ( t_1 \le t_2 \le \cdots \le t_n ), find the maximum length ( L ) of a sequence ( (m_{i_1}, m_{i_2}, \dots, m_{i_L}) ) with ( 1 \le i_1 < i_2 < \cdots < i_L \le n ) satisfying ( m_{i_1} < m_{i_2} < \cdots < m_{i_L} ).

inputFormat

The first line contains a single integer ( n ) (the number of messages). Each of the following ( n ) lines contains two integers: the message ID and the timestamp.

For example: 5 1 1 2 2 3 3 4 4 5 5

outputFormat

Output a single integer representing the length of the longest strictly increasing sequence of message IDs (after sorting the messages by their timestamps).## sample

5
1 1
2 2
3 3
4 4
5 5

5