COCI '23 Contest 3 #3 Milano C.le

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

Silvia is at the Milano Centrale railway station and she noticed that the station has a lot of platforms. She thought that there are too many of them, so she decided to check how many of them are actually needed.

Silvia also noticed an interesting fact that holds at this station: the schedule of arrivals and departures repeats every two days, and additionally, the schedule is such that all $n$ ~n~ trains arrive at the station on one day, and leave the station on the other day. Note that in this way no train will leave before all trains have arrived.

The platforms at the station are long enough so that all $n$ ~n~ trains can be lined up one after another on the same platform. However, if train $x$ ~x~ enters the platform first, and then train $y$ ~y~, then train $x$ ~x~ cannot leave the platform before train $y$ ~y~.

The illustration shows a possible train schedule on the platforms in the second sample test.
The labels on the train i : a_i/b_i denote that the $i$ ~i~-th train will arrive $a_i$ ~a_i~-th at the station on the first day, and leave the station $b_i$ ~b_i~-th on the second day.
The train (2 : 1/2) cannot leave the platform before the train (4 : 5/1).

Silvia is interested in what is the minimum number of platforms needed so that all trains can be lined up on the platforms, without the possibility that a train cannot leave the platform because there is a train in front of it that has not yet left.

Input Specification

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

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

The third line contains $n$ ~n~ integers $b_i$ ~b_i~, $(1 \le b_i \le n, b_i \neq b_j \forall i \neq j)$ , which denotes that the $i$ ~i~-th train leaves the station as the $b_i$ ~b_i~-th train on the second day. The sequence $(b_i)$ ~(b_i)~ is a permutation of the first $n$ ~n~ positive integers.

Output Specification

In the first and only line you should output the minimum number of platforms needed.

Scoring

Subtask	Points	Constraints
1	21	$n \le 10$ ~n \le 10~
2	18	The minimum number of platforms needed will be either $1$ ~1~ or $2$ ~2~.
3	31	$n \le 1\,000$ ~n \le 1\,000~
4	40	No additional constraints.

Sample Input 1

5
3 5 2 4 1
3 2 5 1 4

Sample Output 1

Sample Input 2

5
3 1 2 5 4
4 2 3 1 5

Sample Output 2

Explanation for Sample 2

Take a look at the illustration in the statement.

Sample Input 3

3
3 2 1
1 2 3