시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 37 32 69.565%

문제

동혁이는 화학을 매우 싫어한다. 어느날 화학시간이었다. 선생님은 앞에서 아브가드로의 법칙을 설명하고 있었다. 아보가드로의 법칙은 모든 기체는 같은 온도, 같은 압력에서 같은 부피속에 같은 개수의 입자(분자)를 포함한다는 내용이다. 게다가 기체 분자는 화학적, 물리적 특성과는 무관하게 같은 온도와 압력에서 기체 시료가 차지하는 부피는 기체의 mol수(분자 수)에 비례한다. 예를 들면 분자의 mol수(분자 수)를 2배하면 부피도 2배가 된다는 것이다.

지루해진 동혁이는 3*N크기의 표를 그렸다. 그리고, 첫째 줄에 1부터 N까지 숫자를 임의의 순서대로 중복없이 적었다. 둘째 줄과 셋째 줄에도 1부터 N까지 숫자를 적었는데, 이때 같은 숫자를 여러 번 적기도 했다. 

이제 동혁이는 이 표에서 열을 적절히 지운 뒤, 각 행을 오름 차순으로 정렬했을 때, 각 열에 있는 숫자가 모두 일치하게 하려고 한다.

동혁이가 지워야 하는 열의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 열의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 3개의 줄에는 표에 적혀있는 순서대로 N개의 수가 주어진다.

모든 숫자는 1보다 크거나 같고, N보다 작거나 같으며, 첫째 줄에는 모든 숫자가 한 번씩 나온다.

출력

동혁이가 지워야 하는 열의 최소 개수를 출력한다.

예제 입력 1

7
5 4 3 2 1 6 7
5 5 1 1 3 4 7
3 7 1 4 5 6 2

예제 출력 1

4

힌트

2, 4, 6, 7번째 열을 지우면 된다. 이렇게 지우고 난 뒤, 정렬을 하면 모든 행에 있는 숫자는 1, 3, 5이다.

W3sicHJvYmxlbV9pZCI6IjI5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViMjkwXHViMGEwIFx1ZDY1NFx1ZDU1OVx1YzJkY1x1YWMwNFx1Yzc3NFx1YzVjOFx1YjJlNC4gXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWM1NDRcdWJlMGNcdWFjMDBcdWI0ZGNcdWI4NWNcdWM3NTggXHViYzk1XHVjZTU5XHVjNzQ0IFx1YzEyNFx1YmE4NVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YzU0NFx1YmNmNFx1YWMwMFx1YjRkY1x1Yjg1Y1x1Yzc1OCBcdWJjOTVcdWNlNTlcdWM3NDAgXHViYWE4XHViNGUwIFx1YWUzMFx1Y2NiNFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjNjI4XHViM2M0LCBcdWFjMTlcdWM3NDAgXHVjNTU1XHViODI1XHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWJkODBcdWQ1M2NcdWMxOGRcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWM3ODVcdWM3OTAoXHViZDg0XHVjNzkwKVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTRcdWIyOTQgXHViMGI0XHVjNmE5XHVjNzc0XHViMmU0LiBcdWFjOGNcdWIyZTRcdWFjMDAgXHVhZTMwXHVjY2I0IFx1YmQ4NFx1Yzc5MFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM4MDEsIFx1YmIzY1x1YjlhY1x1YzgwMSBcdWQyYjlcdWMxMzFcdWFjZmNcdWIyOTQgXHViYjM0XHVhZDAwXHVkNTU4XHVhYzhjIFx1YWMxOVx1Yzc0MCBcdWM2MjhcdWIzYzRcdWM2NDAgXHVjNTU1XHViODI1XHVjNWQwXHVjMTFjIFx1YWUzMFx1Y2NiNCBcdWMyZGNcdWI4Y2NcdWFjMDAgXHVjYzI4XHVjOWMwXHVkNTU4XHViMjk0IFx1YmQ4MFx1ZDUzY1x1YjI5NCBcdWFlMzBcdWNjYjRcdWM3NTggbW9sXHVjMjE4KFx1YmQ4NFx1Yzc5MCBcdWMyMTgpXHVjNWQwIFx1YmU0NFx1Yjg0MFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWJkODRcdWM3OTBcdWM3NTggbW9sXHVjMjE4KFx1YmQ4NFx1Yzc5MCBcdWMyMTgpXHViOTdjIDJcdWJjMzBcdWQ1NThcdWJhNzQgXHViZDgwXHVkNTNjXHViM2M0IDJcdWJjMzBcdWFjMDAgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjOWMwXHViOGU4XHVkNTc0XHVjOWM0IFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCAzKk5cdWQwNmNcdWFlMzBcdWM3NTggXHVkNDVjXHViOTdjIFx1YWRmOFx1YjgzOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM5MTFcdWJjZjVcdWM1YzZcdWM3NzQgXHVjODAxXHVjNWM4XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVhY2ZjIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIzYzQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDFcdWM1YzhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YjU0YyBcdWFjMTlcdWM3NDAgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzVlY1x1YjdlYyBcdWJjODggXHVjODAxXHVhZTMwXHViM2M0IFx1ZDU4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHVjODFjIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVkNDVjXHVjNWQwXHVjMTFjIFx1YzVmNFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjOWMwXHVjNmI0IFx1YjRhNCwgXHVhYzAxIFx1ZDU4OVx1Yzc0NCBcdWM2MjRcdWI5ODQgXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWMwMSBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjZTU4XHVkNTU4XHVhYzhjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWM5YzBcdWM2Y2NcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmNFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNDVjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyAzXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ0NWNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1YzYyOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdDIsIDQsIDYsIDdcdWJjODhcdWM5ZjggXHVjNWY0XHVjNzQ0IFx1YzljMFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM5YzBcdWM2YjBcdWFjZTAgXHViMDljIFx1YjRhNCwgXHVjODE1XHViODJjXHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWIyOTQgMSwgMywgNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBVk9HQURSTyIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBpcyBzbGFja2luZyBhZ2FpbiBkdXJpbmcgY2hlbWlzdHJ5IGNsYXNzLCB3aGlsZSB0aGUgdGVhY2hlciBpcyBleHBsYWluaW5nIEF2b2dhZHJvJiMzOTtzIGxhdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBmaXJzdCBkcmV3IGEgdGFibGUgY29uc2lzdGluZyBvZiAzIHJvd3MgYW5kIE4gY29sdW1ucy4gVGhlbiBoZSB3cm90ZSB0aGUgbnVtYmVycyAxIHRvIE4gaW50byB0aGUgZmlyc3Qgcm93IGluIGFyYml0cmFyeSBvcmRlciwgZWFjaCBudW1iZXIgYXBwZWFyaW5nIGV4YWN0bHkgb25jZS4gSW4gdGhlIG90aGVyIHR3byByb3dzIGhlIGFsc28gd3JvdGUgaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCBOLCBidXQgZGlkbiYjMzk7dCBjYXJlIGhvdyBtYW55IHRpbWVzIGEgbnVtYmVyIGFwcGVhcmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MdWthIGNhbiBub3cgZGVsZXRlIGFueSBzZXQgb2YgY29sdW1ucyBmcm9tIHRoZSB0YWJsZS4gQWZ0ZXIgZG9pbmcgc28sIGhlIHNvcnRzIHRoZSBudW1iZXJzIGluIGVhY2ggcm93IGluIGFzY2VuZGluZyBvcmRlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGUgd2FudHMgdG8gb2J0YWluIGEgdGFibGUgaW4gd2hpY2ggYWxsIHRocmVlIHJvd3MgYXJlIGlkZW50aWNhbCBhZnRlciBzb3J0aW5nLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgY29sdW1ucyBoZSBtdXN0IGRlbGV0ZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiBjb2x1bW5zIGluIHRoZSB0YWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyB0aHJlZSBsaW5lcyBjb250YWluIE4gaW50ZWdlcnMgZWFjaCwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZSBudW1iZXJzIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCBOLCBhbmQgdGhlcmUgd2lsbCBiZSBubyBkdXBsaWNhdGVzIGluIHRoZSBmaXJzdCByb3cuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgY29sdW1ucyBMdWthIG11c3QgZGVsZXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+THVrYSBuZWVkcyB0byBkZWxldGUgdGhlIHNlY29uZCwgZm91cnRoLCBzaXh0aCBhbmQgc2V2ZW50aCBjb2x1bW5zLiBBZnRlciBkZWxldGluZyB0aGUgY29sdW1ucyBhbmQgc29ydGluZyBlYWNoIHJvdywgYWxsIHRocmVlIHJvd3MgY29udGFpbiB0aGUgbnVtYmVycyAxLCAzIGFuZCA1LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d