Fewest announcements: hints, no solution

A clinic wants to broadcast announcements over the speakers. Each appointment is a closed range [start, end] of integer minutes, and a patient hears an announcement made at integer minute t whenever start <= t <= end, with both ends included. Ranges of length zero, where start equals end, are allowed.

Return the smallest number of announcements, at times of your choosing, that lets every appointment hear at least one. Appointments come in no particular order and may overlap or repeat. With no appointments, no announcement is needed.

Examples

Input

appointments = [[1, 4], [2, 6], [8, 9], [5, 7]]

Output

3

Note

An announcement at minute 6 serves 2 to 6 and 5 to 7; minute 4 serves 1 to 4; and 8 to 9 needs its own, so three.

Input

appointments = [[1, 2], [2, 3]]

Output

1

Note

Both ranges include minute 2, so one announcement is enough.

Input

appointments = [[5, 5]]

Output

1

Note

A single appointment needs one announcement.

Constraints

• 0 <= appointments.length <= 120000
• 0 <= start <= end <= 1000000
• Times are whole minutes

Hint 1: a nudge

Take the appointment that finishes first. Any announcement that serves it must fall inside its range, so where inside that range would serve the most other appointments?

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