Cinematography

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Charlie Chaplin is seen as one of the most influential cinematographers of all time, rising to fame during the era of silent film. During this era, film was projected onto the big screen from a roll of tape. The film is connected from beginning to end, meaning after the film finishes rolling, it is looped back to the start and played again. At a screening of one of his films, Charlie Chaplin notices that the film roll is misaligned in the projector, causing the movie to start from somewhere in the middle of the film. Help determine how much Charlie Chaplin needs to adjust the roll to achieve the correct timing.

Input Specification

The first line of input contains n (1 \le n \le 10^5) representing the number of frames in the film.
The next line contains n space separated unique integers ranging from n_i (1 \le n_i \le n). This represents the correct ordering of the frames.
The final line contains the same sequence of space separated unique integers in the same order but shifted a certain amount. Integers at the end are looped back to the start.

Output Specification

Output a single integer representing minimum the number of frames Charlie Chaplin must shift the film left or right.

Sample Input

6
1 4 3 2 5 6
3 2 5 6 1 4

Sample Output

2

Explanation for Sample

The film can be shifted 2 frames to the right to achieve the correct order. After shifting once, the order becomes 4 3 2 5 6 1. After shifting again, it becomes 1 4 3 2 5 6 which matches the correct order.


Comments

There are no comments at the moment.