시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 229 81 69 35.204%

문제

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

농장에는 일자형 길이 있고, 양쪽에 목초지가 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMFx1Yjg1Y1x1YzljMFx1Yjk3NFx1YjI5NCBcdWMzMGRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNDQ1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCAoUGxhdGludW0pIiwiZGVzY3JpcHRpb24iOiI8cD5XaHkgZGlkIHRoZSBjb3cgY3Jvc3MgdGhlIHJvYWQ/IFdlIG1heSBuZXZlciBrbm93IHRoZSBmdWxsIHJlYXNvbiwgYnV0IGl0IGlzIGNlcnRhaW4gdGhhdCBGYXJtZXIgSm9obiYjMzk7cyBjb3dzIGRvIGVuZCB1cCBjcm9zc2luZyB0aGUgcm9hZCBxdWl0ZSBmcmVxdWVudGx5LiBJbiBmYWN0LCB0aGV5IGVuZCB1cCBjcm9zc2luZyB0aGUgcm9hZCBzbyBvZnRlbiB0aGF0IHRoZXkgb2Z0ZW4gYnVtcCBpbnRvIGVhY2gtb3RoZXIgd2hlbiB0aGVpciBwYXRocyBjcm9zcywgYSBzaXR1YXRpb24gRmFybWVyIEpvaG4gd291bGQgbGlrZSB0byByZW1lZHkuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIHJhaXNlcyZuYnNwO04mbmJzcDticmVlZHMgb2YgY293cyAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKSwgYW5kIGVhY2ggb2YgaGlzIGZpZWxkcyBpcyBkZWRpY2F0ZWQgdG8gZ3JhemluZyBmb3Igb25lIHNwZWNpZmljIGJyZWVkOyBmb3IgZXhhbXBsZSwgYSBmaWVsZCBkZWRpY2F0ZWQgdG8gYnJlZWQgMTIgY2FuIG9ubHkgYmUgdXNlZCBmb3IgY293cyBvZiBicmVlZCAxMiBhbmQgbm90IG9mIGFueSBvdGhlciBicmVlZC4gQSBsb25nIHJvYWQgcnVucyB0aHJvdWdoIGhpcyBmYXJtLiBUaGVyZSBpcyBhIHNlcXVlbmNlIG9mJm5ic3A7TiZuYnNwO2ZpZWxkcyBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZCAob25lIGZvciBlYWNoIGJyZWVkKSwgYW5kIGEgc2VxdWVuY2Ugb2YmbmJzcDtOJm5ic3A7ZmllbGRzIG9uIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByb2FkIChhbHNvIG9uZSBmb3IgZWFjaCBicmVlZCkuIFdoZW4gYSBjb3cgY3Jvc3NlcyB0aGUgcm9hZCwgc2hlIHRoZXJlZm9yZSBjcm9zc2VzIGJldHdlZW4gdGhlIHR3byBmaWVsZHMgZGVzaWduYXRlZCBmb3IgaGVyIHNwZWNpZmljIGJyZWVkLjxcL3A+XHJcblxyXG48cD5IYWQgRmFybWVyIEpvaG4gcGxhbm5lZCBtb3JlIGNhcmVmdWxseSwgaGUgd291bGQgaGF2ZSBvcmRlcmVkIHRoZSBmaWVsZHMgYnkgYnJlZWQgdGhlIHNhbWUgd2F5IG9uIGJvdGggc2lkZXMgb2YgdGhlIHJvYWQsIHNvIHRoZSB0d28gZmllbGRzIGZvciBlYWNoIGJyZWVkIHdvdWxkIGJlIGRpcmVjdGx5IGFjcm9zcyB0aGUgcm9hZCBmcm9tIGVhY2gtb3RoZXIuIFRoaXMgd291bGQgaGF2ZSBhbGxvd2VkIGNvd3MgdG8gY3Jvc3MgdGhlIHJvYWQgd2l0aG91dCBhbnkgY293cyBmcm9tIGRpZmZlcmVudCBicmVlZHMgYnVtcGluZyBpbnRvIG9uZS1hbm90aGVyLiBBbGFzLCB0aGUgb3JkZXJpbmdzIG9uIGJvdGggc2lkZXMgb2YgdGhlIHJvYWQgbWlnaHQgYmUgZGlmZmVyZW50LCBzbyBGYXJtZXIgSm9obiBvYnNlcnZlcyB0aGF0IHRoZXJlIG1pZ2h0IGJlIHBhaXJzIG9mIGJyZWVkcyB0aGF0IGNyb3NzLiBBIHBhaXIgb2YgZGlmZmVyZW50IGJyZWVkcyZuYnNwOyhhLGIpIGlzICZxdW90O2Nyb3NzaW5nJnF1b3Q7IGlmIGFueSBwYXRoIGFjcm9zcyB0aGUgcm9hZCBmb3IgYnJlZWQmbmJzcDthJm5ic3A7bXVzdCBpbnRlcnNlY3QgYW55IHBhdGggYWNyb3NzIHRoZSByb2FkIGZvciBicmVlZCZuYnNwO2IuPFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIHdvdWxkIGxpa2UgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBjcm9zc2luZyBwYWlycyBvZiBicmVlZHMuIEZvciBsb2dpc3RpY2FsIHJlYXNvbnMsIGhlIGZpZ3VyZXMgaGUgY2FuIG1vdmUgY293cyBhcm91bmQgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQgc28gdGhlIGZpZWxkcyBvbiB0aGF0IHNpZGUgdW5kZXJnbyBhICZxdW90O2N5Y2xpYyBzaGlmdCZxdW90Oy4gVGhhdCBpcywgZm9yIHNvbWUmbmJzcDswICZsZTsgayAmbHQ7IE4sIGV2ZXJ5IGNvdyByZS1sb2NhdGVzIHRvIHRoZSBmaWVsZCZuYnNwO2smbmJzcDtmaWVsZHMgYWhlYWQgb2YgaXQsIHdpdGggdGhlIGNvd3MgaW4gdGhlIGxhc3QmbmJzcDtrJm5ic3A7ZmllbGRzIG1vdmluZyBzbyB0aGV5IG5vdyBwb3B1bGF0ZSB0aGUgZmlyc3QmbmJzcDtrJm5ic3A7ZmllbGRzLiBGb3IgZXhhbXBsZSwgaWYgdGhlIGZpZWxkcyBvbiBvbmUgc2lkZSBvZiB0aGUgcm9hZCBzdGFydCBvdXQgb3JkZXJlZCBieSBicmVlZCBhcyAzLCA3LCAxLCAyLCA1LCA0LCA2IGFuZCB1bmRlcmdvIGEgY3ljbGljIHNoaWZ0IGJ5Jm5ic3A7az0yLCB0aGUgbmV3IG9yZGVyIHdpbGwgYmUgNCwgNiwgMywgNywgMSwgMiwgNS4gUGxlYXNlIGRldGVybWluZSB0aGUgbWluaW11bSBwb3NzaWJsZSBudW1iZXIgb2YgY3Jvc3NpbmcgcGFpcnMgb2YgYnJlZWRzIHRoYXQgY2FuIGV4aXN0IGFmdGVyIGFuIGFwcHJvcHJpYXRlIGN5Y2xpYyBzaGlmdCBvZiB0aGUgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOLiBUaGUgbmV4dCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQ7IGVhY2ggYnJlZWQgSUQgaXMgYW4gaW50ZWdlciBpbiB0aGUgcmFuZ2UmbmJzcDsxJmhlbGxpcDtOLiBUaGUgbGFzdCBOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgdGhlIGZpZWxkcyBvbiB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgcm9hZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGxlYXNlIG91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2YgY3Jvc3NpbmcgcGFpcnMgb2YgYnJlZWRzIGFmdGVyIGEgY3ljbGljIHNoaWZ0IG9mIHRoZSBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQgKGVpdGhlciBzaWRlIGNhbiBiZSBzaGlmdGVkKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==