Ôn Tốt Nghiệp


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type

Sau khi thi xong HSGQG vào lớp 12, cậu không may mắn lấy được suất miễn thi tốt nghiệp. Vì vậy, cậu vẫn tiếp tục phải ôn tập cho kì thi này. Tuy nhiên, mọi thứ không quá khó khi cậu chỉ cần đạt đủ điểm tốt nghiệp. Nhưng cậu không chọn như vậy, cậu chọn tiếp tục ôn để hơn thua với các bạn trong lớp. Trong suốt thời điểm đó, cậu ôn tập cùng nhóm bạn của cậu.

Trong những ngày cuối, cậu và mọi người tập trung luyện đề. Có tất cả \(N\) đề được cả nhóm sưu tầm được, chúng được đánh số từ 1 đến \(N\). Nhóm bạn dự kiến sẽ làm theo thứ tự \(a_1,a_2, ...,a_N\), tức là ngày thứ \(i\) sẽ làm đề \(a_i\). Còn cậu lại muốn khác biệt, cậu làm theo thứ tự \(b_1,b_2,...,b_N\). Tuy nhiên, là một người thích sự khác biệt đơn giản, cậu quyết định thay đổi thứ tự làm đề sao cho số ngày làm đề khác mọi người là nhỏ nhất, bằng cách đưa đề cậu dự định làm đầu tiên xuống cuối cùng. Tức là từ dãy thứ tự \(b_1, b_2, ..., b_N\), trở thành, \(b_2, b_3, ..., b_N, b_1\).

Cậu sẽ thực hiện thao tác đó một vài lần sao cho số lượng ngày cậu làm đề khác mọi người là nhỏ nhất. Tức là, số lượng chỉ số \(i\) thỏa mãn \(a_i \neq b_i\) là tối thiểu. Hãy cho biết số ngày tối thiểu đó là bao nhiêu?

Dữ liệu

  • Dòng đầu tiên chứa một số nguyên dương \(N \ (1\le N \le 10^6)\);
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i \ (1 \le a_i \le N; a_i \neq a_j \forall i\neq j)\);
  • Dòng cuối cùng chứa \(N\) số nguyên dương \(b_i \ (1 \le b_i \le N; b_i \neq b_j \forall i\neq j)\).

Kết quả

  • Kết quả bài toán.

Chấm điểm

  • Subtask 1 (50%): \(N \le 10^3\).
  • Subtask 2 (50%): Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

5
1 2 3 4 5
2 3 4 1 5

output

2

Comments

There are no comments at the moment.