milano — COCI CONTEST_#3
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 13
Algorithms: binary search

# Task Milano C.le

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:

![](_page_0_Picture_5.jpeg)

the schedule of arrivals and departures repeats every two days, and additionally, the schedule is such that all *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* trains can be lined up one after another on the same platform. However, if train *x* enters the platform first, and then train *y*, then train *x* cannot leave the platform before train *y*.

![](_page_0_Figure_8.jpeg)

*The illustration shows a possible train schedule on the platforms in the second sample test. The labels on the train 'i : ai/bi' denote that the i-th train will arrive ai-th at the station on the first day, and leave the station bi-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

The first line contains an integer *n* (1 ≤ *n* ≤ 2 ⋅ 10<sup>5</sup>), the number of trains.

The second line contains *n* integers *a<sub>i</sub>*, (1 ≤ *a<sub>i</sub>* ≤ *n*, *a<sub>i</sub>* ≠ *a<sub>j</sub>* for all *i* ≠ *j*), which denote that the *i*-th train arrives at the station as the *a<sub>i</sub>*-th train on the first day. The sequence (*a<sub>i</sub>*) is a permutation.

The third line contains *n* integers *b<sub>i</sub>*, (1 ≤ *b<sub>i</sub>* ≤ *n*, *b<sub>i</sub>* ≠ *b<sub>j</sub>* for all *i* ≠ *j*), which denote that the *i*-th train leaves the station as the *b<sub>i</sub>*-th train on the second day. The sequence (*b<sub>i</sub>*) is a permutation.

### Output

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

### Scoring

| Subtask | Points | Constraints                                                   |
|---------|--------|---------------------------------------------------------------|
| 1       | 21     | $n \leq 10$                                                    |
| 2       | 18     | The minimum number of platforms needed will be either 1 or 2. |
| 3       | 31     | $n \leq 1000$                                                  |
| 4       | 40     | No additional constraints.                                    |

## Examples

| input                       | input                       | input               |
|-----------------------------|-----------------------------|---------------------|
| 5<br>3 5 2 4 1<br>3 2 5 1 4 | 5<br>3 1 2 5 4<br>4 2 3 1 5 | 3<br>3 2 1<br>1 2 3 |
| output                      | output                      | output              |
| 2                           | 4                           | 1                   |

#### Clarification of the second example:

Take a look at the illustration in the statement.

#### Clarification of the third example:

All the trains can be lined up on the same platform without any problems.

Starter code: