Task

Given a set of intervals, find the maximum number of non-overlapping intervals that can be selected. Use the greedy algorithm: sort intervals by end time, then greedily select each interval whose start time is >= the end time of the last selected interval (touching at an endpoint is allowed). This is the classic activity-selection problem.

Input

• Line 1: n — number of intervals
• Lines 2 to n+1: start end — integer start and end time of each interval

Output

Print a single integer: the maximum number of non-overlapping intervals.

Example

Input:

4
1 3
2 4
3 5
0 6

Output:

2

Scaffolding

Submit a Python file defining:

def max_non_overlapping(intervals: list[list[int]]) -> int:
    ...

Receives a list of [start, end] pairs and returns the maximum count of non-overlapping intervals that can be selected.