시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 278 116 103 43.644%

문제

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'~'Z')와 숫자('0'~'9')로만 이루어져 있다.

출력

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

예제 입력 1

4
ZG431SN
ZG5080K
ST123D
ZG206A
ZG206A
ZG431SN
ZG5080K
ST123D

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjIwMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkOTRcdWM2ZDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc0NCBcdWJlNDRcdWI4NmZcdWQ1NWMgXHViMzAwXHViZDgwXHViZDg0XHVjNzU4IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWQxMzBcdWIxMTAgXHViMGI0XHVjNWQwXHVjMTFjXHVjNzU4IFx1Y2MyOFx1YzEyMCBcdWJjYzBcdWFjYmRcdWM3NDQgXHViYzk1XHViOTYwXHViODVjIFx1YWUwOFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzg3MFx1YWUwOFx1YjljYyBcdWFkMDBcdWNjMzBcdWI4MjVcdWM3NzQgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NFx1Yjc3Y1x1YmE3NCBcdWQxMzBcdWIxMTAgXHViMGI0XHViZDgwXHVjNWQwXHVjMTFjXHViMjk0IFx1Y2MyOFx1YzEyMFx1Yzc3NCBcdWQzMGNcdWMxMjBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzJlNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1Y2MyOFx1YzEyMFx1Yzc0NCBcdWJjYzBcdWFjYmRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1Yzc0Y1x1Yzc0NCBcdWI5ZDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkMTMwXHViMTEwIFx1YjBiNFx1YmQ4MFx1YzVkMFx1YzExY1x1Yzc1OCBcdWNkOTRcdWM2ZDRcdWM3NDAgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWJiMzhcdWIwOWMgXHViYTg1XHVjZjY0XHViZTQ0IFx1YWNiZFx1Y2MzMCBcdWIzMDBcdWFkZmNcdWM3NzRcdWM2NDAgXHVjNjAxXHVjMmRkXHVjNzc0XHVhYzAwIFx1Y2Q5NFx1YzZkNFx1ZDU1OFx1YjI5NCBcdWNjMjhcdWI3YzlcdWM3NDQgXHVjN2ExXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NWMgXHVkMTMwXHViMTEwXHVjNWQwIFx1ZDIyY1x1Yzc4NVx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMzAwXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM3ODVcdWFkNmNcdWM1ZDAsIFx1YzYwMVx1YzJkZFx1Yzc3NFx1YjI5NCBcdWQxMzBcdWIxMTBcdWM3NTggXHVjZDljXHVhZDZjXHVjNWQwIFx1YWMwMVx1YWMwMSBcdWM3YTBcdWJjZjVcdWQ1NThcdWFjZTAsIFx1YjMwMFx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjMjhcdWFjMDAgXHVkMTMwXHViMTEwXHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMsIFx1YzYwMVx1YzJkZFx1Yzc3NFx1YjI5NCBcdWNjMjhcdWFjMDAgXHVkMTMwXHViMTEwXHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVhYzAxXHVhYzAxIFx1Y2MyOFx1YjdjOSBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjODAxXHVjNWI0IFx1YjQ1MFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YWMxY1x1Yzc1OCBcdWNjMjhcdWI3YzlcdWM3NzQgXHVjOWMwXHViMDk4XHVhYzA0IFx1ZDZjNCwgXHViMzAwXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzYwMVx1YzJkZFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWI0ZTRcdWM3NzQgXHVjODAxXHVjNWI0IFx1YjQ1NCBcdWNjMjhcdWI3YzkgXHViYzg4XHVkNjM4XHVjNzU4IFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWJjZjRcdWFjZTAsIFx1ZDEzMFx1YjExMCBcdWIwYjRcdWJkODBcdWM1ZDBcdWMxMWMgXHViYzE4XHViNGRjXHVjMmRjIFx1Y2Q5NFx1YzZkNFx1Yzc0NCBcdWQ1ODhcdWM3NDQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzVlY1x1YWNhOFx1YzljMFx1YjI5NCBcdWNjMjhcdWI0ZTRcdWM3NzQgXHViYTg3IFx1YjMwMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YjMwMFx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM2MDFcdWMyZGRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjZDFkIDJOKzFcdWFjMWNcdWM3NTggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHVjNzU4IFx1YjMwMFx1YzIxOCBOKDEmbGU7TiZsZTsxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjMwMFx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4MDFcdWM3NDAgXHVjYzI4XHViN2M5IFx1YmM4OFx1ZDYzOCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBOKzJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzYwMVx1YzJkZFx1Yzc3NFx1YWMwMCBcdWM4MDFcdWM3NDAgXHVjYzI4XHViN2M5IFx1YmM4OFx1ZDYzOCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjYzI4XHViN2M5IFx1YmM4OFx1ZDYzOFx1YjI5NCA2XHVhZTAwXHVjNzkwIFx1Yzc3NFx1YzBjMSA4XHVhZTAwXHVjNzkwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMsIFx1YzYwMVx1YzViNCBcdWIzMDBcdWJiMzhcdWM3OTAoJiMzOTtBJiMzOTt+JiMzOTtaJiMzOTspXHVjNjQwIFx1YzIyYlx1Yzc5MCgmIzM5OzAmIzM5O34mIzM5OzkmIzM5OylcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDEzMFx1YjExMCBcdWIwYjRcdWJkODBcdWM1ZDBcdWMxMWMgXHViYzE4XHViNGRjXHVjMmRjIFx1Y2Q5NFx1YzZkNFx1Yzc0NCBcdWQ1ODhcdWM3NDQgXHVhYzgzXHVjNzNjXHViODVjIFx1YzVlY1x1YWNhOFx1YzljMFx1YjI5NCBcdWNjMjhcdWFjMDAgXHViYTg3IFx1YjMwMFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAwMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRVTk5FTCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gc3RhbmRzIGF0IHRoZSBlbnRyYW5jZSBhbmQgU2xhdmtvIHN0YW5kcyBhdCB0aGUgZXhpdCBvZiB0aGUgdHVubmVsLiBUaGV5IG5vdGUgdGhlIHJlZ2lzdHJhdGlvbiBwbGF0ZXMgb2YgY2FycyB0aGF0IHBhc3MgYnkgdGhlbSBhbmQgcHJvdmlkZSB0aGF0IGluZm9ybWF0aW9uIHRvIHBvbGljZSBwYXRyb2wgdGhhdCBpcyBhIGZldyBtaWxlcyBkb3duIHRoZSByb2FkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Vc2luZyB0aGUgaW5mb3JtYXRpb24gdGhhdCBNaXJrbyBhbmQgU2xhdmtvIGdhdmUgdGhlbSwgcG9saWNlIGNhbiBkZXRlcm1pbmUsIHdpdGhvdXQgbWFraW5nIG1pc3Rha2UsIHRoYXQgc29tZSBkcml2ZXJzIG1hZGUgYW4gb3ZlcnRha2Ugd2hpbGUgZHJpdmluZyB0aHJvdWdoIHRoZSB0dW5uZWwsIHdoaWNoIGlzIHN0cmljdGx5IGZvcmJpZGRlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgbnVtYmVyIG9mIGRyaXZlcnMgZm9yIHdoaWNoIHRoZSBwb2xpY2UgY2FuIGNlcnRhaW5seSBjbGFpbSB0aGF0IHRoZXkgbWFkZSBhbiBvdmVydGFrZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2UgYXNzdW1lIHRoYXQgdHJhZmZpYyB0aHJvdWdoIHRoZSB0dW5uZWwgd2FzIHdpdGhvdXQgYW55IHN0b3BzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgZmlsZSBjb25zaXN0IG9mIDJOKzEgbGluZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGZpcnN0IGxpbmUgdGhlcmUgaXMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDEwMDAsIG51bWJlciBvZiBjYXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBuZXh0IE4gbGluZXMgdGhlcmUgYXJlIHJlZ2lzdHJhdGlvbiBwbGF0ZXMgb2YgdGhvc2UgY2FycywgaW4gb3JkZXIgdGhleSBlbnRlcmVkIHRoZSB0dW5uZWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG5leHQgTiBsaW5lcyB0aGVyZSBhcmUgcmVnaXN0cmF0aW9uIHBsYXRlcyBvZiB0aG9zZSBjYXJzLCBpbiBvcmRlciB0aGV5IGV4aXQgdGhlIHR1bm5lbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmVnaXN0cmF0aW9uIHBsYXRlIG9mIHNvbWUgY2FyIGNvbnNpc3RzIG9mIGF0IGxlYXN0IHNpeCBhbmQgYXQgbW9zdCBlaWdodCBjaGFyYWN0ZXJzIGFuZCBvbmx5IGFsbG93ZWQgY2hhcmFjdGVycyBhcmUgY2FwaXRhbCBsZXR0ZXJzIG9mIEVuZ2xpc2ggYWxwaGFiZXQgKEEtWikgYW5kIGRpZ2l0cyBvZiBkZWNpbWFsIG51bWJlciBzeXN0ZW0gKDAtOSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgZmlsZSBzaG91bGQgYmUgdGhlIG51bWJlciBvZiBkcml2ZXJzIHdobyBwb2xpY2UgY2FuIGNlcnRhaW5seSBwdW5pc2ggZm9yIG1ha2luZyBvdmVydGFrZSBpbiB0aGUgdHVubmVsLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==