Uncovered bookings: hints, no solution

A hospital lists room bookings as [start, end] pairs of minutes, in no particular order. A booking is covered when a different booking in the list contains it, meaning that booking starts at or before it and ends at or after it. If two bookings are identical, each later copy counts as covered by the earlier one, but the earliest copy is not covered by its copies.

Return how many bookings are not covered by any other booking.

Examples

Input

bookings = [[1, 10], [2, 5], [3, 10], [11, 12]]

Output

2

Note

The 2 to 5 and 3 to 10 bookings sit inside 1 to 10; 1 to 10 and 11 to 12 are uncovered.

Input

bookings = [[4, 8], [4, 8], [4, 8]]

Output

1

Note

Only the first copy of the identical bookings is uncovered.

Input

bookings = [[1, 2], [2, 3], [3, 4]]

Output

3

Note

No booking contains another, so all three are uncovered.

Constraints

• 0 <= bookings.length <= 120000
• 0 <= start < end <= 1000000 for every booking
• Bookings may repeat and may be given in any order

Hint 1: a nudge

When is a booking definitely not needed? Think about which single other booking would have to exist for it to be redundant, and compare a small list by hand.

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing