A small station schedules n trains. Train i arrives at time arrival[i] and departs at time departure[i], occupying a platform for the closed interval [arrival[i], departure[i]] — both endpoints included. Two trains may not share a platform at any instant when they are both present; in particular, if one train departs at the exact same time another arrives, they overlap at that instant and require separate platforms.
Determine the minimum number of platforms the station needs so that every train can be accommodated.
Input format
Line 1: an integer n, the number of trains.
Line 2: n space-separated integers, the arrival times (empty line when n = 0).
Line 3: n space-separated integers, the departure times (empty line when n = 0). It is guaranteed that arrival[i] <= departure[i].
Output format
A single integer: the minimum number of platforms required.
Constraints
- 0 <= n <= 100000
- 0 <= arrival[i] <= departure[i] <= 1000000000