Tại sao con bò băng qua đường? Có lẽ chúng ta sẽ không bao giờ biết được đầy đủ nguyên nhân, nhưng chắc chắn đàn bò của Farmer John băng qua đường khá thường xuyên. Thực tế, chúng sang đường nhiều đến mức thường va vào nhau khi đường đi giao nhau, và Farmer John muốn khắc phục tình trạng này.

Farmer John nuôi \(N\) giống bò (\(1 \leq N \leq 100,000\)), và mỗi cánh đồng của ông được dành riêng cho một giống cụ thể; chẳng hạn, một cánh đồng dành cho giống 12 chỉ có thể được bò giống 12 sử dụng, không phải bất kỳ giống nào khác. Một con đường dài chạy qua trang trại của ông. Có một dãy \(N\) cánh đồng ở một phía của con đường (mỗi giống một cánh đồng), và một dãy \(N\) cánh đồng ở phía bên kia (cũng mỗi giống một cánh đồng). Vì vậy, khi một con bò băng qua đường, nó đi giữa hai cánh đồng dành riêng cho giống của mình.

Nếu Farmer John lên kế hoạch cẩn thận hơn, ông đã sắp xếp các cánh đồng theo cùng một thứ tự giống ở hai phía con đường, để hai cánh đồng của mỗi giống nằm đối diện trực tiếp với nhau. Khi đó, bò có thể băng qua đường mà không va vào bò thuộc giống khác. Đáng tiếc là thứ tự ở hai phía có thể khác nhau, nên Farmer John nhận thấy có thể tồn tại những cặp giống giao nhau. Một cặp hai giống khác nhau \((a,b)\) được gọi là "giao nhau" nếu mọi đường đi băng qua đường dành cho giống \(a\) đều bắt buộc phải cắt mọi đường đi băng qua đường dành cho giống \(b\).

Farmer John muốn giảm thiểu số cặp giống giao nhau. Vì lý do hậu cần, ông có thể di chuyển bò ở một phía con đường để các cánh đồng ở phía đó trải qua một phép "dịch vòng". Cụ thể, với một giá trị \(0 \leq k < N\) nào đó, mỗi con bò chuyển đến cánh đồng cách vị trí của nó \(k\) cánh đồng về phía trước, còn những con bò ở \(k\) cánh đồng cuối chuyển đến chiếm \(k\) cánh đồng đầu tiên. Chẳng hạn, nếu ban đầu các cánh đồng ở một phía con đường có thứ tự giống là 3, 7, 1, 2, 5, 4, 6 và được dịch vòng với \(k=2\), thứ tự mới sẽ là 4, 6, 3, 7, 1, 2, 5. Hãy xác định số cặp giống giao nhau nhỏ nhất có thể sau khi thực hiện một phép dịch vòng thích hợp đối với các cánh đồng ở một phía con đường.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo mô tả thứ tự các cánh đồng ở một phía của con đường theo mã số giống; mỗi mã số giống là một số nguyên trong khoảng \(1 \ldots N\). \(N\) dòng cuối cùng mô tả thứ tự các cánh đồng ở phía bên kia của con đường theo mã số giống.

Dữ liệu ra

In ra số cặp giống giao nhau nhỏ nhất sau khi dịch vòng các cánh đồng ở một phía con đường (có thể dịch một trong hai phía).

Ví dụ

5
5
4
1
3
2
1
3
2
5
4

0

Nguồn

USACO 2017 February Contest, Platinum — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=720