시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 97 38 32 40.506%

문제

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

농장에는 일자형 길이 있고, 양쪽에 목초지가 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
W3sicHJvYmxlbV9pZCI6IjE0NDU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWFjMDAgXHVjNjVjIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWIyOTRcdWM5YzBcdWIyOTQgXHViYmY4XHVkNTc0XHVhY2IwIFx1YjA5Y1x1YzgxY1x1YzljMFx1YjljYywgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc1OCBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1Yzc5MFx1YzhmYyBcdWFjNzRcdWIxMGNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjMGFjXHVjMmU0XHVjNzc0XHViMmU0LiBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YjI5NCBcdWM3N2NcdWM3NzQgXHViMTA4XHViYjM0IFx1YzdhNlx1YzU0NFx1YzExYyBcdWFjNzRcdWIxMDhcdWJhNzRcdWMxMWMgXHViZDgwXHViNTJhXHVkNzg4XHViMjk0IFx1Yzc3Y1x1YjNjNCBcdWMwZGRcdWFlMzBcdWIyOTRcdWIzNzAsIFx1Yzg3NFx1Yzc0MCBcdWM3NzQgXHVjMGMxXHVkNjY5XHVjNzQ0IFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjYWJkXHVjNWQwIFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBOXHVhYzFjXHVjNTI5ICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1Yzc4OFx1YjJlNC4gXHVjODg1XHViY2M0XHViODVjIFx1YmFhOVx1Y2QwOFx1YzljMCBcdWFkNmNcdWM4NzBcdWFjMDAgXHViMTA4XHViYjM0IFx1YjJlY1x1Yjc3Y1x1YzExYyBcdWQ1NWMgXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwXHViMjk0IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWM4ODVcdWM3NTggXHVjMThjXHViOWNjIFx1YmMyOVx1YmFhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBpXHViYzg4IFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YjI5NCBpXHViYzg4IFx1YzE4Y1x1YjljYyBcdWJjMjlcdWJhYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzE4Y1x1YWMwMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTEwIFx1YjU0Y1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjODg1XHVjNzQ0IFx1YmMyOVx1YmFhOVx1ZDU1OFx1YjI5NCBcdWJjMThcdWIzMDBcdWQzYjhcdWM3NTggXHViYWE5XHVjZDA4XHVjOWMwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOVx1Y2QwOFx1YzljMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViNGE0XHVjOGZkXHViYzE1XHVjOGZkXHVjNzc0XHVjNWI0XHVjMTFjLCBhXHVjODg1XHVjNzU4IFx1YzE4Y1x1YzY0MCBiXHVjODg1XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM3NzQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YWM3NFx1YzEyNFx1YzVkMCBcdWM4ZmNcdWM3NThcdWI5N2MgXHVhZTMwXHVjNmI4XHVjNzc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQwZDNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YyAoYSxiKVx1Yjk3YyAmcXVvdDtcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkJnF1b3Q7XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVjODc0XHVjNzQwIFx1YWMwMFx1Yjg1Y1x1YzljMFx1Yjk3NFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMThkXHVjN2E1XHVjNzQ0IFx1YzYyZVx1YWUzMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhY2UwXHVjNTQ4XHVkNTg4XHViMmU0LiAwICZsZTsgayAmbHQ7IE5cdWM3NzggXHVjODE1XHVjMjE4IGtcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWI5ZTggXHViNGE0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYTlcdWNkMDhcdWM5YzAga1x1YWMxY1x1Yjk3YyBcdWI5ZTggXHVjNTVlXHVjNzNjXHViODVjIFx1YzYyZVx1YWUzOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjRcdWMxMWMsIFx1YmFhOVx1Y2QwOFx1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIDMsIDcsIDEsIDIsIDUsIDQsIDZcdWM3NzRcdWFjZTAgaz0yXHViNzdjXHViYTc0LCBcdWM2MmVcdWFlMzQgXHVkNmM0XHVjNzU4IFx1YmFhOVx1Y2QwOFx1YzljMCBcdWJjODhcdWQ2MzhcdWIyOTQgNCwgNiwgMywgNywgMSwgMiwgNVx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YWUzOFx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVlY1x1YjNjNCBcdWI0MThcdWFjZTAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHVjNWI0XHViM2M0IFx1YjQxOFx1YzljMFx1YjljYywgXHViNDU4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHViNDFjXHViMmU0LiBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWM4NzRcdWM3NDQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODg1XHVjNzQwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1Yjg1Y1x1YzljMFx1Yjk3NFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTQ0NTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaHkgRGlkIHRoZSBDb3cgQ3Jvc3MgdGhlIFJvYWQgKFBsYXRpbnVtKSIsImRlc2NyaXB0aW9uIjoiPHA+V2h5IGRpZCB0aGUgY293IGNyb3NzIHRoZSByb2FkPyBXZSBtYXkgbmV2ZXIga25vdyB0aGUgZnVsbCByZWFzb24sIGJ1dCBpdCBpcyBjZXJ0YWluIHRoYXQgRmFybWVyIEpvaG4mIzM5O3MgY293cyBkbyBlbmQgdXAgY3Jvc3NpbmcgdGhlIHJvYWQgcXVpdGUgZnJlcXVlbnRseS4gSW4gZmFjdCwgdGhleSBlbmQgdXAgY3Jvc3NpbmcgdGhlIHJvYWQgc28gb2Z0ZW4gdGhhdCB0aGV5IG9mdGVuIGJ1bXAgaW50byBlYWNoLW90aGVyIHdoZW4gdGhlaXIgcGF0aHMgY3Jvc3MsIGEgc2l0dWF0aW9uIEZhcm1lciBKb2huIHdvdWxkIGxpa2UgdG8gcmVtZWR5LjxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiByYWlzZXMmbmJzcDtOJm5ic3A7YnJlZWRzIG9mIGNvd3MgKDEgJmxlOyBOICZsZTsgMTAwLDAwMCksIGFuZCBlYWNoIG9mIGhpcyBmaWVsZHMgaXMgZGVkaWNhdGVkIHRvIGdyYXppbmcgZm9yIG9uZSBzcGVjaWZpYyBicmVlZDsgZm9yIGV4YW1wbGUsIGEgZmllbGQgZGVkaWNhdGVkIHRvIGJyZWVkIDEyIGNhbiBvbmx5IGJlIHVzZWQgZm9yIGNvd3Mgb2YgYnJlZWQgMTIgYW5kIG5vdCBvZiBhbnkgb3RoZXIgYnJlZWQuIEEgbG9uZyByb2FkIHJ1bnMgdGhyb3VnaCBoaXMgZmFybS4gVGhlcmUgaXMgYSBzZXF1ZW5jZSBvZiZuYnNwO04mbmJzcDtmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQgKG9uZSBmb3IgZWFjaCBicmVlZCksIGFuZCBhIHNlcXVlbmNlIG9mJm5ic3A7TiZuYnNwO2ZpZWxkcyBvbiB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgcm9hZCAoYWxzbyBvbmUgZm9yIGVhY2ggYnJlZWQpLiBXaGVuIGEgY293IGNyb3NzZXMgdGhlIHJvYWQsIHNoZSB0aGVyZWZvcmUgY3Jvc3NlcyBiZXR3ZWVuIHRoZSB0d28gZmllbGRzIGRlc2lnbmF0ZWQgZm9yIGhlciBzcGVjaWZpYyBicmVlZC48XC9wPlxyXG5cclxuPHA+SGFkIEZhcm1lciBKb2huIHBsYW5uZWQgbW9yZSBjYXJlZnVsbHksIGhlIHdvdWxkIGhhdmUgb3JkZXJlZCB0aGUgZmllbGRzIGJ5IGJyZWVkIHRoZSBzYW1lIHdheSBvbiBib3RoIHNpZGVzIG9mIHRoZSByb2FkLCBzbyB0aGUgdHdvIGZpZWxkcyBmb3IgZWFjaCBicmVlZCB3b3VsZCBiZSBkaXJlY3RseSBhY3Jvc3MgdGhlIHJvYWQgZnJvbSBlYWNoLW90aGVyLiBUaGlzIHdvdWxkIGhhdmUgYWxsb3dlZCBjb3dzIHRvIGNyb3NzIHRoZSByb2FkIHdpdGhvdXQgYW55IGNvd3MgZnJvbSBkaWZmZXJlbnQgYnJlZWRzIGJ1bXBpbmcgaW50byBvbmUtYW5vdGhlci4gQWxhcywgdGhlIG9yZGVyaW5ncyBvbiBib3RoIHNpZGVzIG9mIHRoZSByb2FkIG1pZ2h0IGJlIGRpZmZlcmVudCwgc28gRmFybWVyIEpvaG4gb2JzZXJ2ZXMgdGhhdCB0aGVyZSBtaWdodCBiZSBwYWlycyBvZiBicmVlZHMgdGhhdCBjcm9zcy4gQSBwYWlyIG9mIGRpZmZlcmVudCBicmVlZHMmbmJzcDsoYSxiKSBpcyAmcXVvdDtjcm9zc2luZyZxdW90OyBpZiBhbnkgcGF0aCBhY3Jvc3MgdGhlIHJvYWQgZm9yIGJyZWVkJm5ic3A7YSZuYnNwO211c3QgaW50ZXJzZWN0IGFueSBwYXRoIGFjcm9zcyB0aGUgcm9hZCBmb3IgYnJlZWQmbmJzcDtiLjxcL3A+XHJcblxyXG48cD5GYXJtZXIgSm9obiB3b3VsZCBsaWtlIHRvIG1pbmltaXplIHRoZSBudW1iZXIgb2YgY3Jvc3NpbmcgcGFpcnMgb2YgYnJlZWRzLiBGb3IgbG9naXN0aWNhbCByZWFzb25zLCBoZSBmaWd1cmVzIGhlIGNhbiBtb3ZlIGNvd3MgYXJvdW5kIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkIHNvIHRoZSBmaWVsZHMgb24gdGhhdCBzaWRlIHVuZGVyZ28gYSAmcXVvdDtjeWNsaWMgc2hpZnQmcXVvdDsuIFRoYXQgaXMsIGZvciBzb21lJm5ic3A7MCAmbGU7IGsgJmx0OyBOLCBldmVyeSBjb3cgcmUtbG9jYXRlcyB0byB0aGUgZmllbGQmbmJzcDtrJm5ic3A7ZmllbGRzIGFoZWFkIG9mIGl0LCB3aXRoIHRoZSBjb3dzIGluIHRoZSBsYXN0Jm5ic3A7ayZuYnNwO2ZpZWxkcyBtb3Zpbmcgc28gdGhleSBub3cgcG9wdWxhdGUgdGhlIGZpcnN0Jm5ic3A7ayZuYnNwO2ZpZWxkcy4gRm9yIGV4YW1wbGUsIGlmIHRoZSBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQgc3RhcnQgb3V0IG9yZGVyZWQgYnkgYnJlZWQgYXMgMywgNywgMSwgMiwgNSwgNCwgNiBhbmQgdW5kZXJnbyBhIGN5Y2xpYyBzaGlmdCBieSZuYnNwO2s9MiwgdGhlIG5ldyBvcmRlciB3aWxsIGJlIDQsIDYsIDMsIDcsIDEsIDIsIDUuIFBsZWFzZSBkZXRlcm1pbmUgdGhlIG1pbmltdW0gcG9zc2libGUgbnVtYmVyIG9mIGNyb3NzaW5nIHBhaXJzIG9mIGJyZWVkcyB0aGF0IGNhbiBleGlzdCBhZnRlciBhbiBhcHByb3ByaWF0ZSBjeWNsaWMgc2hpZnQgb2YgdGhlIGZpZWxkcyBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zJm5ic3A7Ti4gVGhlIG5leHQmbmJzcDtOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkOyBlYWNoIGJyZWVkIElEIGlzIGFuIGludGVnZXIgaW4gdGhlIHJhbmdlJm5ic3A7MSZoZWxsaXA7Ti4gVGhlIGxhc3QgTiZuYnNwO2xpbmVzIGRlc2NyaWJlIHRoZSBvcmRlciwgYnkgYnJlZWQgSUQsIG9mIHRoZSBmaWVsZHMgb24gdGhlIG90aGVyIHNpZGUgb2YgdGhlIHJvYWQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGNyb3NzaW5nIHBhaXJzIG9mIGJyZWVkcyBhZnRlciBhIGN5Y2xpYyBzaGlmdCBvZiB0aGUgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkIChlaXRoZXIgc2lkZSBjYW4gYmUgc2hpZnRlZCkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d