시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 95 36 31 38.750%

문제

소가 왜 길을 건너는지는 미해결 난제지만, 농부 존의 소들이 길을 자주 건넌다는 것은 잘 알려진 사실이다. 소들이 길을 건너는 일이 너무 잦아서 건너면서 부딪히는 일도 생기는데, 존은 이 상황을 해결하고 싶다.

농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 (1 ≤ N ≤ 100,000) 있다. 종별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종의 소만 방목할 수 있다. i번 목초지에는 i번 소만 방목할 수 있는 것이다. 소가 길을 건널 때는 자신의 종을 방목하는 반대편의 목초지로 이동하는 것이다.

목초지의 순서가 뒤죽박죽이어서, a종의 소와 b종의 소가 건너는 길이 겹칠 수도 있다. 존이 목초지 건설에 주의를 기울이지 않은 탓이다. 이 때 (a,b)를 "가로지르는 쌍"이라고 하자.

존은 가로지르는 쌍의 수를 최소화하기 위해 농장을 옮기는 방법을 고안했다. 0 ≤ k < N인 정수 k에 대해, 맨 뒤에 있는 목초지 k개를 맨 앞으로 옮길 것이다. 예를 들어서, 목초지 번호가 차례대로 3, 7, 1, 2, 5, 4, 6이고 k=2라면, 옮긴 후의 목초지 번호는 4, 6, 3, 7, 1, 2, 5가 된다. 길의 왼쪽에 있는 목초지여도 되고 오른쪽이어도 되지만, 둘 중 하나만 된다. 가로지르는 쌍을 최소로 할 수 있도록 존을 도와주자.

입력

첫 줄에 N이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

가로지르는 쌍의 최소 개수를 출력한다.

예제 입력 1

5
5
4
1
3
2
1
3
2
5
4

예제 출력 1

0
W3sicHJvYmxlbV9pZCI6IjE0NDU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWFjMDAgXHVjNjVjIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWIyOTRcdWM5YzBcdWIyOTQgXHViYmY4XHVkNTc0XHVhY2IwIFx1YjA5Y1x1YzgxY1x1YzljMFx1YjljYywgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc1OCBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1Yzc5MFx1YzhmYyBcdWFjNzRcdWIxMGNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjMGFjXHVjMmU0XHVjNzc0XHViMmU0LiBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YjI5NCBcdWM3N2NcdWM3NzQgXHViMTA4XHViYjM0IFx1YzdhNlx1YzU0NFx1YzExYyBcdWFjNzRcdWIxMDhcdWJhNzRcdWMxMWMgXHViZDgwXHViNTJhXHVkNzg4XHViMjk0IFx1Yzc3Y1x1YjNjNCBcdWMwZGRcdWFlMzBcdWIyOTRcdWIzNzAsIFx1Yzg3NFx1Yzc0MCBcdWM3NzQgXHVjMGMxXHVkNjY5XHVjNzQ0IFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjYWJkXHVjNWQwIFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBOXHVhYzFjXHVjNTI5ICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1Yzc4OFx1YjJlNC4gXHVjODg1XHViY2M0XHViODVjIFx1YmFhOVx1Y2QwOFx1YzljMCBcdWFkNmNcdWM4NzBcdWFjMDAgXHViMTA4XHViYjM0IFx1YjJlY1x1Yjc3Y1x1YzExYyBcdWQ1NWMgXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwXHViMjk0IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWM4ODVcdWM3NTggXHVjMThjXHViOWNjIFx1YmMyOVx1YmFhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBpXHViYzg4IFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YjI5NCBpXHViYzg4IFx1YzE4Y1x1YjljYyBcdWJjMjlcdWJhYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTEwIFx1YjU0Y1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjODg1XHVjNzQ0IFx1YmMyOVx1YmFhOVx1ZDU1OFx1YjI5NCBcdWJjMThcdWIzMDBcdWQzYjhcdWM3NTggXHViYWE5XHVjZDA4XHVjOWMwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOVx1Y2QwOFx1YzljMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViNGE0XHVjOGZkXHViYzE1XHVjOGZkXHVjNzc0XHVjNWI0XHVjMTFjLCBhXHVjODg1XHVjNzU4IFx1YzE4Y1x1YzY0MCBiXHVjODg1XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM3NzQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YWM3NFx1YzEyNFx1YzVkMCBcdWM4ZmNcdWM3NThcdWI5N2MgXHVhZTMwXHVjNmI4XHVjNzc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQwZDNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgKGEsYilcdWI5N2MgJnF1b3Q7XHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YzMwZCZxdW90O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc0MCBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjE4ZFx1YzdhNVx1Yzc0NCBcdWM2MmVcdWFlMzBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWNlMFx1YzU0OFx1ZDU4OFx1YjJlNC4gMCAmbGU7IGsgJmx0OyBOXHVjNzc4IFx1YzgxNVx1YzIxOCBrXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHViOWU4IFx1YjRhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwIGtcdWFjMWNcdWI5N2MgXHViOWU4IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM2MmVcdWFlMzggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0XHVjMTFjLCBcdWJhYTlcdWNkMDhcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyAzLCA3LCAxLCAyLCA1LCA0LCA2XHVjNzc0XHVhY2UwIGs9Mlx1Yjc3Y1x1YmE3NCwgXHVjNjJlXHVhZTM0IFx1ZDZjNFx1Yzc1OCBcdWJhYTlcdWNkMDhcdWM5YzAgXHViYzg4XHVkNjM4XHViMjk0IDQsIDYsIDMsIDcsIDEsIDIsIDVcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFlMzhcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWNkMDhcdWM5YzBcdWM1ZWNcdWIzYzQgXHViNDE4XHVhY2UwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc3NFx1YzViNFx1YjNjNCBcdWI0MThcdWM5YzBcdWI5Y2MsIFx1YjQ1OCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOWNjIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YzMwZFx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjODc0XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Yzg4NVx1Yzc0MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIChQbGF0aW51bSkiLCJkZXNjcmlwdGlvbiI6IjxwPldoeSBkaWQgdGhlIGNvdyBjcm9zcyB0aGUgcm9hZD8gV2UgbWF5IG5ldmVyIGtub3cgdGhlIGZ1bGwgcmVhc29uLCBidXQgaXQgaXMgY2VydGFpbiB0aGF0IEZhcm1lciBKb2huJiMzOTtzIGNvd3MgZG8gZW5kIHVwIGNyb3NzaW5nIHRoZSByb2FkIHF1aXRlIGZyZXF1ZW50bHkuIEluIGZhY3QsIHRoZXkgZW5kIHVwIGNyb3NzaW5nIHRoZSByb2FkIHNvIG9mdGVuIHRoYXQgdGhleSBvZnRlbiBidW1wIGludG8gZWFjaC1vdGhlciB3aGVuIHRoZWlyIHBhdGhzIGNyb3NzLCBhIHNpdHVhdGlvbiBGYXJtZXIgSm9obiB3b3VsZCBsaWtlIHRvIHJlbWVkeS48XC9wPlxyXG5cclxuPHA+RmFybWVyIEpvaG4gcmFpc2VzJm5ic3A7TiZuYnNwO2JyZWVkcyBvZiBjb3dzICgxICZsZTsgTiAmbGU7IDEwMCwwMDApLCBhbmQgZWFjaCBvZiBoaXMgZmllbGRzIGlzIGRlZGljYXRlZCB0byBncmF6aW5nIGZvciBvbmUgc3BlY2lmaWMgYnJlZWQ7IGZvciBleGFtcGxlLCBhIGZpZWxkIGRlZGljYXRlZCB0byBicmVlZCAxMiBjYW4gb25seSBiZSB1c2VkIGZvciBjb3dzIG9mIGJyZWVkIDEyIGFuZCBub3Qgb2YgYW55IG90aGVyIGJyZWVkLiBBIGxvbmcgcm9hZCBydW5zIHRocm91Z2ggaGlzIGZhcm0uIFRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YmbmJzcDtOJm5ic3A7ZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkIChvbmUgZm9yIGVhY2ggYnJlZWQpLCBhbmQgYSBzZXF1ZW5jZSBvZiZuYnNwO04mbmJzcDtmaWVsZHMgb24gdGhlIG90aGVyIHNpZGUgb2YgdGhlIHJvYWQgKGFsc28gb25lIGZvciBlYWNoIGJyZWVkKS4gV2hlbiBhIGNvdyBjcm9zc2VzIHRoZSByb2FkLCBzaGUgdGhlcmVmb3JlIGNyb3NzZXMgYmV0d2VlbiB0aGUgdHdvIGZpZWxkcyBkZXNpZ25hdGVkIGZvciBoZXIgc3BlY2lmaWMgYnJlZWQuPFwvcD5cclxuXHJcbjxwPkhhZCBGYXJtZXIgSm9obiBwbGFubmVkIG1vcmUgY2FyZWZ1bGx5LCBoZSB3b3VsZCBoYXZlIG9yZGVyZWQgdGhlIGZpZWxkcyBieSBicmVlZCB0aGUgc2FtZSB3YXkgb24gYm90aCBzaWRlcyBvZiB0aGUgcm9hZCwgc28gdGhlIHR3byBmaWVsZHMgZm9yIGVhY2ggYnJlZWQgd291bGQgYmUgZGlyZWN0bHkgYWNyb3NzIHRoZSByb2FkIGZyb20gZWFjaC1vdGhlci4gVGhpcyB3b3VsZCBoYXZlIGFsbG93ZWQgY293cyB0byBjcm9zcyB0aGUgcm9hZCB3aXRob3V0IGFueSBjb3dzIGZyb20gZGlmZmVyZW50IGJyZWVkcyBidW1waW5nIGludG8gb25lLWFub3RoZXIuIEFsYXMsIHRoZSBvcmRlcmluZ3Mgb24gYm90aCBzaWRlcyBvZiB0aGUgcm9hZCBtaWdodCBiZSBkaWZmZXJlbnQsIHNvIEZhcm1lciBKb2huIG9ic2VydmVzIHRoYXQgdGhlcmUgbWlnaHQgYmUgcGFpcnMgb2YgYnJlZWRzIHRoYXQgY3Jvc3MuIEEgcGFpciBvZiBkaWZmZXJlbnQgYnJlZWRzJm5ic3A7KGEsYikgaXMgJnF1b3Q7Y3Jvc3NpbmcmcXVvdDsgaWYgYW55IHBhdGggYWNyb3NzIHRoZSByb2FkIGZvciBicmVlZCZuYnNwO2EmbmJzcDttdXN0IGludGVyc2VjdCBhbnkgcGF0aCBhY3Jvc3MgdGhlIHJvYWQgZm9yIGJyZWVkJm5ic3A7Yi48XC9wPlxyXG5cclxuPHA+RmFybWVyIEpvaG4gd291bGQgbGlrZSB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIGNyb3NzaW5nIHBhaXJzIG9mIGJyZWVkcy4gRm9yIGxvZ2lzdGljYWwgcmVhc29ucywgaGUgZmlndXJlcyBoZSBjYW4gbW92ZSBjb3dzIGFyb3VuZCBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZCBzbyB0aGUgZmllbGRzIG9uIHRoYXQgc2lkZSB1bmRlcmdvIGEgJnF1b3Q7Y3ljbGljIHNoaWZ0JnF1b3Q7LiBUaGF0IGlzLCBmb3Igc29tZSZuYnNwOzAgJmxlOyBrICZsdDsgTiwgZXZlcnkgY293IHJlLWxvY2F0ZXMgdG8gdGhlIGZpZWxkJm5ic3A7ayZuYnNwO2ZpZWxkcyBhaGVhZCBvZiBpdCwgd2l0aCB0aGUgY293cyBpbiB0aGUgbGFzdCZuYnNwO2smbmJzcDtmaWVsZHMgbW92aW5nIHNvIHRoZXkgbm93IHBvcHVsYXRlIHRoZSBmaXJzdCZuYnNwO2smbmJzcDtmaWVsZHMuIEZvciBleGFtcGxlLCBpZiB0aGUgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkIHN0YXJ0IG91dCBvcmRlcmVkIGJ5IGJyZWVkIGFzIDMsIDcsIDEsIDIsIDUsIDQsIDYgYW5kIHVuZGVyZ28gYSBjeWNsaWMgc2hpZnQgYnkmbmJzcDtrPTIsIHRoZSBuZXcgb3JkZXIgd2lsbCBiZSA0LCA2LCAzLCA3LCAxLCAyLCA1LiBQbGVhc2UgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIHBvc3NpYmxlIG51bWJlciBvZiBjcm9zc2luZyBwYWlycyBvZiBicmVlZHMgdGhhdCBjYW4gZXhpc3QgYWZ0ZXIgYW4gYXBwcm9wcmlhdGUgY3ljbGljIHNoaWZ0IG9mIHRoZSBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyZuYnNwO04uIFRoZSBuZXh0Jm5ic3A7TiZuYnNwO2xpbmVzIGRlc2NyaWJlIHRoZSBvcmRlciwgYnkgYnJlZWQgSUQsIG9mIGZpZWxkcyBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZDsgZWFjaCBicmVlZCBJRCBpcyBhbiBpbnRlZ2VyIGluIHRoZSByYW5nZSZuYnNwOzEmaGVsbGlwO04uIFRoZSBsYXN0IE4mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiB0aGUgZmllbGRzIG9uIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByb2FkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2Ugb3V0cHV0IHRoZSBtaW5pbXVtIG51bWJlciBvZiBjcm9zc2luZyBwYWlycyBvZiBicmVlZHMgYWZ0ZXIgYSBjeWNsaWMgc2hpZnQgb2YgdGhlIGZpZWxkcyBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZCAoZWl0aGVyIHNpZGUgY2FuIGJlIHNoaWZ0ZWQpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==