A car-sharing service has n bookings for a single car. Booking i reserves the car for the half-open time range [start_i, end_i). Two bookings conflict if their ranges overlap (sharing any instant); bookings that merely touch (one ends exactly when another begins) do not conflict. The service must cancel the minimum number of bookings so that no two of the remaining bookings conflict. Print that minimum number of cancellations.
Input format
Line 1: an integer n.
Next n lines: two integers start_i end_i describing booking i.
Output format
A single integer: the minimum number of bookings that must be cancelled.
Constraints
- 1 <= n <= 14
- 0 <= start_i < end_i <= 1000