시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 42 36 69.231%

문제

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

W3sicHJvYmxlbV9pZCI6IjI5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWQ2NTRcdWQ1NTlcdWMyZGNcdWFjMDRcdWM3NzRcdWM1YzhcdWIyZTQuIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViZTBjXHVhYzAwXHViNGRjXHViODVjXHVjNzU4IFx1YmM5NVx1Y2U1OVx1Yzc0NCBcdWMxMjRcdWJhODVcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWNcdWM3NTggXHViYzk1XHVjZTU5XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWFlMzBcdWNjYjRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzYyOFx1YjNjNCwgXHVhYzE5XHVjNzQwIFx1YzU1NVx1YjgyNVx1YzVkMFx1YzExYyBcdWFjMTlcdWM3NDAgXHViZDgwXHVkNTNjXHVjMThkXHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWFjMWNcdWMyMThcdWM3NTggXHVjNzg1XHVjNzkwKFx1YmQ4NFx1Yzc5MClcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0XHViMjk0IFx1YjBiNFx1YzZhOVx1Yzc3NFx1YjJlNC4gXHVhYzhjXHViMmU0XHVhYzAwIFx1YWUzMFx1Y2NiNCBcdWJkODRcdWM3OTBcdWIyOTQgXHVkNjU0XHVkNTU5XHVjODAxLCBcdWJiM2NcdWI5YWNcdWM4MDEgXHVkMmI5XHVjMTMxXHVhY2ZjXHViMjk0IFx1YmIzNFx1YWQwMFx1ZDU1OFx1YWM4YyBcdWFjMTlcdWM3NDAgXHVjNjI4XHViM2M0XHVjNjQwIFx1YzU1NVx1YjgyNVx1YzVkMFx1YzExYyBcdWFlMzBcdWNjYjQgXHVjMmRjXHViOGNjXHVhYzAwIFx1Y2MyOFx1YzljMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWQ1M2NcdWIyOTQgXHVhZTMwXHVjY2I0XHVjNzU4IG1vbFx1YzIxOChcdWJkODRcdWM3OTAgXHVjMjE4KVx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHViZDg0XHVjNzkwXHVjNzU4IG1vbFx1YzIxOChcdWJkODRcdWM3OTAgXHVjMjE4KVx1Yjk3YyAyXHViYzMwXHVkNTU4XHViYTc0IFx1YmQ4MFx1ZDUzY1x1YjNjNCAyXHViYzMwXHVhYzAwIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzljMFx1YjhlOFx1ZDU3NFx1YzljNCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgMypOXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDQ1Y1x1Yjk3YyBcdWFkZjhcdWI4MzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOTExXHViY2Y1XHVjNWM2XHVjNzc0IFx1YzgwMVx1YzVjOFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YWNmYyBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViM2M0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODAxXHVjNWM4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI1NGMgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzgwMVx1YWUzMFx1YjNjNCBcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YzgxYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1ZDQ1Y1x1YzVkMFx1YzExYyBcdWM1ZjRcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YzljMFx1YzZiNCBcdWI0YTQsIFx1YWMwMSBcdWQ1ODlcdWM3NDQgXHVjNjI0XHViOTg0IFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDQ1Y1x1Yzc1OCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgM1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNDVjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNWY0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQyLCA0LCA2LCA3XHViYzg4XHVjOWY4IFx1YzVmNFx1Yzc0NCBcdWM5YzBcdWM2YjBcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjOWMwXHVjNmIwXHVhY2UwIFx1YjA5YyBcdWI0YTQsIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWQ1NThcdWJhNzQgXHViYWE4XHViNGUwIFx1ZDU4OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IDEsIDMsIDVcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQVZPR0FEUk8iLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgc2xhY2tpbmcgYWdhaW4gZHVyaW5nIGNoZW1pc3RyeSBjbGFzcywgd2hpbGUgdGhlIHRlYWNoZXIgaXMgZXhwbGFpbmluZyBBdm9nYWRybyYjMzk7cyBsYXcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EgZmlyc3QgZHJldyBhIHRhYmxlIGNvbnNpc3Rpbmcgb2YgMyByb3dzIGFuZCBOIGNvbHVtbnMuIFRoZW4gaGUgd3JvdGUgdGhlIG51bWJlcnMgMSB0byBOIGludG8gdGhlIGZpcnN0IHJvdyBpbiBhcmJpdHJhcnkgb3JkZXIsIGVhY2ggbnVtYmVyIGFwcGVhcmluZyBleGFjdGx5IG9uY2UuIEluIHRoZSBvdGhlciB0d28gcm93cyBoZSBhbHNvIHdyb3RlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgTiwgYnV0IGRpZG4mIzM5O3QgY2FyZSBob3cgbWFueSB0aW1lcyBhIG51bWJlciBhcHBlYXJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBjYW4gbm93IGRlbGV0ZSBhbnkgc2V0IG9mIGNvbHVtbnMgZnJvbSB0aGUgdGFibGUuIEFmdGVyIGRvaW5nIHNvLCBoZSBzb3J0cyB0aGUgbnVtYmVycyBpbiBlYWNoIHJvdyBpbiBhc2NlbmRpbmcgb3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIHdhbnRzIHRvIG9idGFpbiBhIHRhYmxlIGluIHdoaWNoIGFsbCB0aHJlZSByb3dzIGFyZSBpZGVudGljYWwgYWZ0ZXIgc29ydGluZy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgaGUgbXVzdCBkZWxldGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgY29sdW1ucyBpbiB0aGUgdGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdGhyZWUgbGluZXMgY29udGFpbiBOIGludGVnZXJzIGVhY2gsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGUgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgTiwgYW5kIHRoZXJlIHdpbGwgYmUgbm8gZHVwbGljYXRlcyBpbiB0aGUgZmlyc3Qgcm93LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgTHVrYSBtdXN0IGRlbGV0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkx1a2EgbmVlZHMgdG8gZGVsZXRlIHRoZSBzZWNvbmQsIGZvdXJ0aCwgc2l4dGggYW5kIHNldmVudGggY29sdW1ucy4gQWZ0ZXIgZGVsZXRpbmcgdGhlIGNvbHVtbnMgYW5kIHNvcnRpbmcgZWFjaCByb3csIGFsbCB0aHJlZSByb3dzIGNvbnRhaW4gdGhlIG51bWJlcnMgMSwgMyBhbmQgNS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==