Problem A
Air Conditioned Minions
You are the boss of ACM (Air Conditioned Minions), an upstanding company with a single goal of world domination.
The company has
You are planning to construct several rooms in your new hideout, and assign your minions there. You fix the temperature of each room to any value you want (different rooms may have different temperatures). After you fix the temperatures, you will assign each of your minions to these rooms (a room can hold any number of minions). You want all minions to like the temperatures of their assigned rooms. Each minion likes an interval of temperature, and these preferences will be given to you.
Air conditioners are very expensive to maintain. Thus, you want to construct as few rooms as possible. What is the minimum number of rooms you need to set up such that it would be possible to assign minions to rooms as discussed earlier?
Input
The first line contains a non-negative integer
Output
Print an integer denoting the minimum number of rooms you need to construct.
Sample Data Explanation
In the first example, one of the possible solutions is to
setup two rooms — one with temperature
Sample Input 1 | Sample Output 1 |
---|---|
3 1 2 2 4 5 6 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
5 1 2 3 5 4 6 7 9 8 10 |
3 |