Chocolate#7253
Chocolate bars produced by the confectionery company «Yum Yum» are designed as long 1 \times N bars, each consisting of squares. Each square displays one of renowned confectioners. On different bars, these same confectioners appear in varying sequences.
Task. Develop a program that, given the sequence of portraits on two chocolate bars, calculates the minimum number of segments the first bar needs to be divided into so that, by rearranging these segments, the sequence on the second bar can be achieved. The bar can only be broken at the edges of the squares, and neither the bar nor its segments can be flipped.
The first line contains a natural number (2 \le N \le 10^5), representing the number of squares in the chocolate bar. Each confectioner is numbered from to . The second and third lines each contain distinct natural numbers (each not exceeding ), representing the order of portraits on the first and second bars, respectively. It is guaranteed that these sequences are different.
Print a single number — the minimum number of segments into which the first bar must be broken so that, by rearranging these segments, the sequence of portraits on the second bar can be achieved.
Example 1
The first bar can be divided into four segments: square , square , two squares and , and square . By rearranging these segments, the sequence of portraits on the second bar can be matched. No division into three or fewer segments will allow the formation of the same sequence as on the second bar.
The test set is divided into 4 blocks, each with specific conditions:
20 points: 2 \le N \le 3
20 points: 3 < N \le 6
30 points: 6 < N \le 1000
30 points: 1000 < N \le 10^5