Minimal Pizza Pile Stacking for HackCCO

Troy is perfecting his latest plan—“HackCCO”! As everyone knows, the biggest attraction at a hackathon is the free food. To ensure hackCCO is an unprecedented success, Troy ordered a truck loaded with n pizzas. The pizza at position \(i\) from the top of the truck has flavor \(a_i\). When the truck arrives, Troy has to stack these pizzas on a long table. He unloads the pizzas one by one from the truck and, for each pizza, he can either place it on top of an existing pile or start a new pile.

There are also n hungry HackCCO participants lining up. The \(i\)th participant has a favorite pizza flavor \(b_i\). When the \(i\)th participant reaches the table, if there is any pile whose top pizza has flavor \(b_i\), the participant will take one such pizza (they choose arbitrarily if there are multiple); otherwise, they leave hungry.

Troy does not want anyone to leave hungry. Your task is to help him determine whether there exists a way to stack the pizzas (i.e. to decide for each pizza whether to put it on an existing pile or start a new one) so that every participant finds at least one pile with their favorite flavor when it is their turn, no matter which matching pizza they take. If there is one or more valid stacking arrangements, you should find one that minimizes the total number of piles created. Output the minimum number of piles required; if it is impossible to satisfy all participants, output -1.

Note: The pizzas come in the fixed order \(a_1, a_2, \dots, a_n\) (from the truck), and the participants arrive in order \(b_1, b_2, \dots, b_n\). When a participant takes a pizza from a pile, that pizza is removed and the next pizza below (if any) becomes the new top. The stacking decision you make must guarantee that no matter which available pile a participant chooses (if there are multiple with top flavor equal to their favorite), all participants can eventually get a pizza they like.

Hint: You may think of the problem as matching each pizza to a participant who will remove it. If a pizza with flavor \(v\) appears as the \(r\)th occurrence in \(a\), and among the participants with favorite flavor \(v\) the positions in the queue are \(j_1 < j_2 < \dots < j_k\), it is optimal to assign the pizza the value \(j_{k-r+1}\) (i.e. assign the earliest pizza the latest possible removal time) in order to form as long a stack as possible. The answer is then the minimum number of stacks (i.e. the minimum chain decomposition into decreasing sequences) which equals the length of the longest increasing subsequence in the resulting removal times.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) — the number of pizzas and participants.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) denotes the flavor of the \(i\)th pizza from the top of the truck.

The third line contains \(n\) integers \(b_1, b_2, \dots, b_n\) where \(b_i\) is the favorite flavor of the \(i\)th participant.

It is guaranteed that the total number of pizzas for each flavor in \(a\) is the same as the total number of participants who prefer that flavor in \(b\).

outputFormat

If there exists a stacking arrangement that ensures every participant gets a pizza they like regardless of which valid choice they make, output the minimum number of piles required. Otherwise, output -1.

sample

5
1 2 1 2 1
1 1 1 2 2

2