Woburn Challenge 2017-18 Round 3 - Senior Division

You've assembled a set of ~N~ ~(1 \le N \le 300\,000)~ Twitch clips from a live stream by your favourite twitch.tv streamer. A clip is a video fragment of the stream, and the ~i~-th clip encapsulates the exclusive time interval from ~A_i~ to ~B_i~ seconds into the stream ~(0 \le A_i < B_i \le 10^9)~. The clips are not all guaranteed to be distinct.

In an effort to convince your friends to start watching this stream and join you in spamming its chat, you plan to show them some of the clips. You'd like to choose the smallest possible subset ~S~ of the clips which still offer a good representation of the whole stream. In particular, each of the ~N~ total clips must have some time in common with at least one clip in ~S~. A pair of clips have some time in common with each other if there's a positive amount of time from the stream which is present in both clips - in other words, if the intersection of their exclusive time intervals is non-empty. For example, clips with time intervals ~(0, 5)~ and ~(4, 10)~ have some time in common, while clips with time intervals ~(0, 5)~ and ~(5, 10)~ do not.

Can you determine the minimum possible number of clips which ~S~ can be made up of?

Subtasks

In test cases worth ~5/23~ of the points, ~N \le 15~.
In test cases worth another ~11/23~ of the points, ~N \le 1\,000~.

Input Specification

The first line of input consists of a single integer, ~N~.
~N~ lines follow, the ~i~-th of which consists of two space-separated integers, ~A_i~ and ~B_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the minimum possible number of clips which ~S~ can be made up of.

Sample Input

6
11 14
14 23
5 22
12 28
2 6
22 31

Sample Output

2

Sample Explanation

No single clip can be chosen such that all ~5~ other clips have some time in common with it. However, there are various valid sets ~S~ made up of ~2~ clips, such as clips ~4~ ~(12 \dots 28)~ and ~5~ ~(2 \dots 6)~.