A tram terminal must serve n trams in one day. Tram i arrives at time arrival[i] and departs at time departure[i], with arrival[i] ≤ departure[i]. A tram occupies a platform for the whole closed interval [arrival[i], departure[i]], and a platform can hold only one tram at any instant. If one tram departs at exactly the same time another arrives, they still both need the platform at that instant, so they require two different platforms.
Find the minimum number of platforms so that every tram can be served.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the arrival times.
Line 3: n space-separated integers, the departure times.
Output format
A single integer: the minimum number of platforms required.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ arrival[i] ≤ departure[i] ≤ 1000000000