Maximum Contests

You are given n contests, each with a starting time and an ending time. You want to participate in as many contests as possible. However, you must participate in every contest you register for, and you cannot participate in more than one contest at the same time.

Formally, you are given n intervals. The i-th contest is represented by a starting time s_i and an ending time e_i with the property that \(e_i > s_i\). You need to select a subset of these contests such that no two chosen contests overlap in time, and the size of the subset is maximized.

Input Constraints:

• \(1 \leq n \leq 10^5\)
• \(0 \leq s_i < e_i \leq 10^9\)

It is assumed that if one contest ends at time t, you can start another contest at the same time t.

inputFormat

The first line contains an integer n, the number of contests.

Each of the following n lines contains two integers, s_i and e_i, representing the starting and ending time of the i-th contest.

outputFormat

Output a single integer representing the maximum number of contests that can be attended.

sample

1
1 2

1