Maximum Non-Overlapping Events

You are given a collection of n events. Each event is defined by a start and an end time. Your task is to determine the maximum number of events you can attend, provided that you can only attend one event at a time, i.e., the events you attend must not overlap in time.

Formally, given n events with start time \( s_i \) and end time \( e_i \), find the maximum number \( k \) such that there exists a subset of events \( \{(s_{i_1}, e_{i_1}), \ldots, (s_{i_k}, e_{i_k})\} \) satisfying \( e_{i_j} \leq s_{i_{j+1}} \) for all \( 1 \leq j < k \).

You are required to read input from standard input and output the result to standard output.

inputFormat

The input is given in the following format:

 n
 s1 e1
 s2 e2
 ...
 sn en

Here, n is an integer representing the number of events, and for each event, s and e are integers denoting the start and end times respectively.

outputFormat

Print a single integer denoting the maximum number of non-overlapping events that can be attended.

4
1 4
2 3
3 5
6 8

3