Khớp dãy bằng phép xoay vòng

Bối cảnh

Hai thiết bị ghi cùng một chuỗi tín hiệu trên một vòng tròn, nhưng thiết bị thứ hai có thể bắt đầu ghi từ một vị trí khác. Dãy B được xem là khớp với A nếu tồn tại số bước k sao cho sau khi xoay A sang phải k bước, A trở thành đúng B. Nếu có nhiều k do dãy tuần hoàn, cần in k nhỏ nhất. Nếu không có phép xoay nào khớp, in -1.

Không được dùng chuỗi, thuật toán tìm mẫu hay container của các module sau. Với giới hạn n vừa phải, bài Advanced yêu cầu mô hình hóa chính xác chỉ số vòng tròn và kiểm tra có hệ thống tất cả n phép xoay có thể. Khó khăn chủ yếu nằm ở việc ánh xạ vị trí trong B về vị trí tương ứng trong A sau phép xoay và xử lý modulo âm đúng cách.

Đây là phiên bản nâng cấp thực sự của thao tác xoay: thay vì chỉ tạo một rotation, phải suy luận ngược và tìm rotation phù hợp trong không gian n khả năng.

Yêu cầu

1. Thử k từ 0 đến n-1 theo thứ tự tăng.
2. Với mỗi vị trí i của B, phần tử tương ứng trong A trước xoay là (i-k) mod n.
3. Nếu mọi vị trí khớp, in k ngay; nếu hết k thì -1.

Input

Dòng 1: n. Dòng 2: dãy A. Dòng 3: dãy B.

Output

Một số nguyên: k nhỏ nhất để xoay A sang phải thành B, hoặc -1.

Ràng buộc

1 ≤ n ≤ 2000, |A[i]|,|B[i]| ≤ 10^9.

Ví dụ 1

Input

5
1 2 3 4 5
4 5 1 2 3

Output

2

Giải thích

Ta xét phép xoay vòng sang phải k vị trí. Với k=2, dãy A=1 2 3 4 5 trở thành 4 5 1 2 3, đúng bằng B. Với k=0 hoặc k=1 hai dãy chưa khớp, vì vậy 2 là số bước xoay nhỏ nhất và cũng là đáp án đầu tiên được tìm thấy. Output là 2.

Ví dụ 2

Input

4
1 1 1 1
1 1 1 1

Output

0

Giải thích

Cả A và B đều gồm bốn số 1. Ngay ở k=0, hai dãy đã giống nhau hoàn toàn nên không cần xoay. Mặc dù mọi giá trị k khác cũng tạo cùng dãy vì các phần tử bằng nhau, bài cần số bước nhỏ nhất nên kết quả là 0.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: static arrays, cyclic indexing, rotation matching, exhaustive search, modular arithmetic
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100