Yet Another Contest 9 P1 - Permutation Cutting

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Nils likes cutting permutations. He currently has a permutation of the first N positive integers (s_1, s_2, \dots, s_N), and wishes to reorder it to form the permutation (t_1, t_2, \dots, t_N).

Exactly once, he is able to cut his permutation by dividing it into some number of contiguous subsequences, reordering these subsequences, and concatenating them back together. For example, if he starts with the permutation (2, 1, 6, 3, 5, 4), he could split it into the subsequences (2, 1, 6), (3), (5, 4), reorder them to obtain (5, 4), (3), (2, 1, 6), and concatenate them back together to form (5, 4, 3, 2, 1, 6).

What is the minimum number of contiguous subsequences that Nils can divide his permutation into while achieving his goal? Note that it can be shown that Josh can always cut his permutation in a way to achieve his goal.

Constraints

1 \le N \le 2 \times 10 ^ 5

s_1, s_2, \dots, s_N is a permutation of the integers 1, 2, \dots, N, that is, every integer between 1 and N (inclusive) occurs exactly once in s.

t_1, t_2, \dots, t_N is a permutation of the integers 1, 2, \dots, N.

Subtask 1 [60%]

t_i = i for all i.

Subtask 2 [40%]

No additional constraints.

Input Specification

The first line contains a single integer, N.

The second line contains N space-separated integers, s_1, s_2, \dots, s_N.

The third line contains N space-separated integers, t_1, t_2, \dots, t_N.

Output Specification

Output the minimum number of contiguous sequences that Nils can divide his permutation into.

Sample Input 1

5
4 5 1 3 2
1 3 2 5 4

Sample Output 1

3

Explanation for Sample Output 1

Nils can cut his permutation to obtain the contiguous subsequences (4), (5), (1, 3, 2), reorder them to obtain (1, 3, 2), (5), (4), and concatenate them to obtain (1, 3, 2, 5, 4). This is the only optimal cut.

Sample Input 2

2
1 2
1 2

Sample Output 2

1

Comments

There are no comments at the moment.