시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 34 29 67.442%

문제

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

W3sicHJvYmxlbV9pZCI6IjI5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWJjZjRcdWFjMDBcdWI0ZGNcdWI4NWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3NDQgXHViOWU0XHVjNmIwIFx1YzJlYlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjNWI0XHViMjkwXHViMGEwIFx1ZDY1NFx1ZDU1OVx1YzJkY1x1YWMwNFx1Yzc3NFx1YzVjOFx1YjJlNC4gXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWM1NDRcdWJlMGNcdWFjMDBcdWI0ZGNcdWI4NWNcdWM3NTggXHViYzk1XHVjZTU5XHVjNzQ0IFx1YzEyNFx1YmE4NVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YzU0NFx1YmNmNFx1YWMwMFx1YjRkY1x1Yjg1Y1x1Yzc1OCBcdWJjOTVcdWNlNTlcdWM3NDAgXHViYWE4XHViNGUwIFx1YWUzMFx1Y2NiNFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjNjI4XHViM2M0LCBcdWFjMTlcdWM3NDAgXHVjNTU1XHViODI1XHVjNWQwXHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWJkODBcdWQ1M2NcdWMxOGRcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1YWMyZlx1YzIxOFx1Yzc1OCBcdWM3ODVcdWM3OTAoXHViZDg0XHVjNzkwKVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTRcdWIyOTQgXHViMGI0XHVjNmE5XHVjNzc0XHViMmU0LiBcdWFjOGNcdWIyZTRcdWFjMDAgXHVhZTMwXHVjY2I0IFx1YmQ4NFx1Yzc5MFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM4MDEsIFx1YmIzY1x1YjlhY1x1YzgwMSBcdWQyYjlcdWMxMzFcdWFjZmNcdWIyOTQgXHViYjM0XHVhZDAwXHVkNTU4XHVhYzhjIFx1YWMxOVx1Yzc0MCBcdWM2MjhcdWIzYzRcdWM2NDAgXHVjNTU1XHViODI1XHVjNWQwXHVjMTFjIFx1YWUzMFx1Y2NiNCBcdWMyZGNcdWI4Y2NcdWFjMDAgXHVjYzI4XHVjOWMwXHVkNTU4XHViMjk0IFx1YmQ4MFx1ZDUzY1x1YjI5NCBcdWFlMzBcdWNjYjRcdWM3NTggbW9sXHVjMjE4KFx1YmQ4NFx1Yzc5MCBcdWMyMTgpXHVjNWQwIFx1YmU0NFx1Yjg0MFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCBcdWJkODRcdWM3OTBcdWM3NTggbW9sXHVjMjE4KFx1YmQ4NFx1Yzc5MCBcdWMyMTgpXHViOTdjIDJcdWJjMzBcdWQ1NThcdWJhNzQgXHViZDgwXHVkNTNjXHViM2M0IDJcdWJjMzBcdWFjMDAgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjOWMwXHViOGU4XHVkNTc0XHVjOWM0IFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCAzKk5cdWQwNmNcdWFlMzBcdWM3NTggXHVkNDVjXHViOTdjIFx1YWRmOFx1YjgzOFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM5MTFcdWJjZjVcdWM1YzZcdWM3NzQgXHVjODAxXHVjNWM4XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVhY2ZjIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIzYzQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDFcdWM1YzhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWI1NGMgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzgwMVx1YWUzMFx1YjNjNCBcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YzgxYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjNzc0IFx1ZDQ1Y1x1YzVkMFx1YzExYyBcdWM1ZjRcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YzljMFx1YzZiNCBcdWI0YTQsIFx1YWMwMSBcdWQ1ODlcdWM3NDQgXHVjNjI0XHViOTg0IFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1Yzc3Y1x1Y2U1OFx1ZDU1OFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjOWMwXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDQ1Y1x1Yzc1OCBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgM1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNDVjXHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWIwOThcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzljMFx1YzZjY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNWY0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHQyLCA0LCA2LCA3XHViYzg4XHVjOWY4IFx1YzVmNFx1Yzc0NCBcdWM5YzBcdWM2YjBcdWJhNzQgXHViNDFjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjOWMwXHVjNmIwXHVhY2UwIFx1YjA5YyBcdWI0YTQsIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWQ1NThcdWJhNzQgXHViYWE4XHViNGUwIFx1ZDU4OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IDEsIDMsIDVcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQVZPR0FEUk8iLCJkZXNjcmlwdGlvbiI6IjxwPkx1a2EgaXMgc2xhY2tpbmcgYWdhaW4gZHVyaW5nIGNoZW1pc3RyeSBjbGFzcywgd2hpbGUgdGhlIHRlYWNoZXIgaXMgZXhwbGFpbmluZyBBdm9nYWRybyYjMzk7cyBsYXcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkx1a2EgZmlyc3QgZHJldyBhIHRhYmxlIGNvbnNpc3Rpbmcgb2YgMyByb3dzIGFuZCBOIGNvbHVtbnMuIFRoZW4gaGUgd3JvdGUgdGhlIG51bWJlcnMgMSB0byBOIGludG8gdGhlIGZpcnN0IHJvdyBpbiBhcmJpdHJhcnkgb3JkZXIsIGVhY2ggbnVtYmVyIGFwcGVhcmluZyBleGFjdGx5IG9uY2UuIEluIHRoZSBvdGhlciB0d28gcm93cyBoZSBhbHNvIHdyb3RlIGludGVnZXJzIGJldHdlZW4gMSBhbmQgTiwgYnV0IGRpZG4mIzM5O3QgY2FyZSBob3cgbWFueSB0aW1lcyBhIG51bWJlciBhcHBlYXJlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+THVrYSBjYW4gbm93IGRlbGV0ZSBhbnkgc2V0IG9mIGNvbHVtbnMgZnJvbSB0aGUgdGFibGUuIEFmdGVyIGRvaW5nIHNvLCBoZSBzb3J0cyB0aGUgbnVtYmVycyBpbiBlYWNoIHJvdyBpbiBhc2NlbmRpbmcgb3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIHdhbnRzIHRvIG9idGFpbiBhIHRhYmxlIGluIHdoaWNoIGFsbCB0aHJlZSByb3dzIGFyZSBpZGVudGljYWwgYWZ0ZXIgc29ydGluZy4gV3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgaGUgbXVzdCBkZWxldGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgY29sdW1ucyBpbiB0aGUgdGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgdGhyZWUgbGluZXMgY29udGFpbiBOIGludGVnZXJzIGVhY2gsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGUgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgTiwgYW5kIHRoZXJlIHdpbGwgYmUgbm8gZHVwbGljYXRlcyBpbiB0aGUgZmlyc3Qgcm93LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGNvbHVtbnMgTHVrYSBtdXN0IGRlbGV0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkx1a2EgbmVlZHMgdG8gZGVsZXRlIHRoZSBzZWNvbmQsIGZvdXJ0aCwgc2l4dGggYW5kIHNldmVudGggY29sdW1ucy4gQWZ0ZXIgZGVsZXRpbmcgdGhlIGNvbHVtbnMgYW5kIHNvcnRpbmcgZWFjaCByb3csIGFsbCB0aHJlZSByb3dzIGNvbnRhaW4gdGhlIG51bWJlcnMgMSwgMyBhbmQgNS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==