Background

Translated from COCI 2023/2024 Contest #3 T3 “Milano C.le”.

Problem Description

Silvia is currently at Milano Centrale station, and she notices that the station has many platforms. She thinks there are too many platforms, so she decides to count how many platforms are actually needed.

Silvia also notices an interesting fact about this station: the departure and arrival timetable repeats every two days, and the timetable satisfies that all $n$ trains arrive at the station on one day and leave on the other day. Note that in this way, no train will leave before all trains have arrived.

The platforms are long enough so that all $n$ trains can line up on the same platform as a single queue. However, if train $x$ enters a platform before train $y$ enters the same platform, then train $x$ cannot leave before train $y$ leaves the platform.

Silvia wants to know the minimum number of platforms needed to park all trains, under the condition that no train becomes unable to leave because a train in front of it has not left yet.

Input Format

The first line contains an integer $n\ (1\le n\le 2\cdot 10^5)$, denoting the number of trains.

The second line contains $n$ integers $a_i\ (1\le a_i\le n,\forall i\neq j,a_i\neq a_j)$, where the $i$-th train arrives at the station as the $a_i$-th arrival on the first day. The sequence $(a_i)$ is a permutation.

The third line contains $n$ integers $b_i\ (1\le b_i\le n,\forall i\neq j,b_i\neq b_j)$, where the $i$-th train leaves the station as the $b_i$-th departure on the second day. The sequence $(b_i)$ is a permutation.

Output Format

Output one integer in one line, denoting the minimum number of platforms needed.

5
3 5 2 4 1
3 2 5 1 4

2

5
3 1 2 5 4
4 2 3 1 5

4

3
3 2 1
1 2 3

1

Hint

Sample Explanation 2

The figure above shows one possible train arrangement on the platforms for Sample 2. The label $(i:a_i/b_i)$ on a train means that the $i$-th train arrives as the $a_i$-th arrival on the first day and then leaves as the $b_i$-th departure on the second day. Train $(2:1/2)$ cannot leave the platform earlier than train $(4:5/1)$.

Sample Explanation 3

All trains can line up on a single platform without any issues.

Subtasks

Translated by ChatGPT 5