시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB113756674.157%

문제

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

예제 입력 2

9
1 3 5 9 8 6 2 4 7
2 1 5 6 4 9 3 4 7
3 5 1 9 8 6 2 8 7

예제 출력 2

2
W3sicHJvYmxlbV9pZCI6IjI5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViMjkwIFx1YjBhMCBcdWQ2NTRcdWQ1NTlcdWMyZGNcdWFjMDRcdWM3NzRcdWM1YzhcdWIyZTQuIFx1YzEyMFx1YzBkZFx1YjJkOFx1Yzc0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViZTBjXHVhYzAwXHViNGRjXHViODVjXHVjNzU4IFx1YmM5NVx1Y2U1OVx1Yzc0NCBcdWMxMjRcdWJhODVcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWNcdWM3NTggXHViYzk1XHVjZTU5XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWFlMzBcdWNjYjRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzYyOFx1YjNjNCwgXHVhYzE5XHVjNzQwIFx1YzU1NVx1YjgyNVx1YzVkMFx1YzExYyBcdWFjMTlcdWM3NDAgXHViZDgwXHVkNTNjXHVjMThkXHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWFjMWNcdWMyMThcdWM3NTggXHVjNzg1XHVjNzkwKFx1YmQ4NFx1Yzc5MClcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTVjXHViMmU0XHViMjk0IFx1YjBiNFx1YzZhOVx1Yzc3NFx1YjJlNC4gXHVhYzhjXHViMmU0XHVhYzAwIFx1YWUzMFx1Y2NiNCBcdWJkODRcdWM3OTBcdWIyOTQgXHVkNjU0XHVkNTU5XHVjODAxLCBcdWJiM2NcdWI5YWNcdWM4MDEgXHVkMmI5XHVjMTMxXHVhY2ZjXHViMjk0IFx1YmIzNFx1YWQwMFx1ZDU1OFx1YWM4YyBcdWFjMTlcdWM3NDAgXHVjNjI4XHViM2M0XHVjNjQwIFx1YzU1NVx1YjgyNVx1YzVkMFx1YzExYyBcdWFlMzBcdWNjYjQgXHVjMmRjXHViOGNjXHVhYzAwIFx1Y2MyOFx1YzljMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWQ1M2NcdWIyOTQgXHVhZTMwXHVjY2I0XHVjNzU4IG1vbFx1YzIxOChcdWJkODRcdWM3OTAgXHVjMjE4KVx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgXHViZDg0XHVjNzkwXHVjNzU4IG1vbFx1YzIxOChcdWJkODRcdWM3OTAgXHVjMjE4KVx1Yjk3YyAyXHViYzMwXHVkNTU4XHViYTc0IFx1YmQ4MFx1ZDUzY1x1YjNjNCAyXHViYzMwXHVhYzAwIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMFx1YjhlOFx1ZDU3NFx1YzljNCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgMypOXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDQ1Y1x1Yjk3YyBcdWFkZjhcdWI4MzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOTExXHViY2Y1XHVjNWM2XHVjNzc0IFx1YzgwMVx1YzVjOFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YWNmYyBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViM2M0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODAxXHVjNWM4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI1NGMgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzgwMVx1YWUzMFx1YjNjNCBcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1ZDQ1Y1x1YzVkMFx1YzExYyBcdWM1ZjRcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YzljMFx1YzZiNCBcdWI0YTQsIFx1YWMwMSBcdWQ1ODlcdWM3NDQgXHVjNjI0XHViOTg0IFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNDVjXHVjNzU4IFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyAzXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ0NWNcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzAsIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1YzYyOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPjIsIDQsIDYsIDdcdWJjODhcdWM5ZjggXHVjNWY0XHVjNzQ0IFx1YzljMFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM5YzBcdWM2YjBcdWFjZTAgXHViMDljIFx1YjRhNCwgXHVjODE1XHViODJjXHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWIyOTQgMSwgMywgNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyOTg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQVZPR0FEUk8iLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgc2xhY2tpbmcgYWdhaW4gZHVyaW5nIGNoZW1pc3RyeSBjbGFzcywgd2hpbGUgdGhlIHRlYWNoZXIgaXMgZXhwbGFpbmluZyBBdm9nYWRybyYjMzk7cyBsYXcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EgZmlyc3QgZHJldyBhIHRhYmxlIGNvbnNpc3Rpbmcgb2YgMyByb3dzIGFuZCBOIGNvbHVtbnMuIFRoZW4gaGUgd3JvdGUgdGhlIG51bWJlcnMgMSB0byBOIGludG8gdGhlIGZpcnN0IHJvdyBpbiBhcmJpdHJhcnkgb3JkZXIsIGVhY2ggbnVtYmVyIGFwcGVhcmluZyBleGFjdGx5IG9uY2UuIEluIHRoZSBvdGhlciB0d28gcm93cyBoZSBhbHNvIHdyb3RlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgTiwgYnV0IGRpZG4mIzM5O3QgY2FyZSBob3cgbWFueSB0aW1lcyBhIG51bWJlciBhcHBlYXJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBjYW4gbm93IGRlbGV0ZSBhbnkgc2V0IG9mIGNvbHVtbnMgZnJvbSB0aGUgdGFibGUuIEFmdGVyIGRvaW5nIHNvLCBoZSBzb3J0cyB0aGUgbnVtYmVycyBpbiBlYWNoIHJvdyBpbiBhc2NlbmRpbmcgb3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIHdhbnRzIHRvIG9idGFpbiBhIHRhYmxlIGluIHdoaWNoIGFsbCB0aHJlZSByb3dzIGFyZSBpZGVudGljYWwgYWZ0ZXIgc29ydGluZy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgaGUgbXVzdCBkZWxldGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgY29sdW1ucyBpbiB0aGUgdGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdGhyZWUgbGluZXMgY29udGFpbiBOIGludGVnZXJzIGVhY2gsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGUgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgTiwgYW5kIHRoZXJlIHdpbGwgYmUgbm8gZHVwbGljYXRlcyBpbiB0aGUgZmlyc3Qgcm93LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgTHVrYSBtdXN0IGRlbGV0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCBleGFtcGxlLCBMdWthIG5lZWRzIHRvIGRlbGV0ZSB0aGUgc2Vjb25kLCBmb3VydGgsIHNpeHRoIGFuZCBzZXZlbnRoIGNvbHVtbnMuIEFmdGVyIGRlbGV0aW5nIHRoZSBjb2x1bW5zIGFuZCBzb3J0aW5nIGVhY2ggcm93LCBhbGwgdGhyZWUgcm93cyBjb250YWluIHRoZSBudW1iZXJzIDEsIDMgYW5kIDUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #5 4번