시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 175 63 60 38.462%

문제

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일을 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 남자의 키가 밀리미터 단위로 주어진다. 키는 절대값이 1500보다 크거나 같고, 2500보다 작거나 같은 정수이다. 사람의 키는 주어지는 값의 절대값이다. 키가 양수인 경우에는 자신보다 키가 큰 여자와 춤을 추기를 원하는 남자이고, 음수인 경우에는 키가 작은 사람과 춤을 추기를 원하는 남자이다.

셋째 줄에는 여자의 키가 밀리미터 단위로 주어진다. 키의 범위나 의미 역시 남자와 동일하다. 

출력

첫째 줄에 상근이가 만들어 줄 수 있는 쌍의 최댓값을 출력한다.

예제 입력 1

2
-1800 -2200
1900 1700

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDRcdWMyYTQgXHVkMzBjXHVkMmYwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIwYThcdWM3OTAgTlx1YmE4NVx1YWNmYyBcdWM1ZWNcdWM3OTAgTlx1YmE4NVx1Yzc3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOGZjXHVjZDVjXHVkNTVjIFx1YjMwNFx1YzJhNCBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjNjU0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViMGE4XHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM1ZWNcdWM3OTBcdWIyOTQgXHViMGE4XHVjNzkwXHVjNjQwIFx1Y2RhNFx1Yzc0NCBcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWNkYTRcdWM3NDQgXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWIwYThcdWM3OTBcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWIwYThcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YzVlY1x1Yzc5MFx1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YzcyMFx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1ZDU1YyBcdWM3MjBcdWQ2MTVcdWM3NDAgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHVjNWVjXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjNzIwXHVkNjE1XHVjNzQwIFx1Yzc5MFx1YzJlMFx1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzcyMFx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHVjNWVjXHVjNzkwXHViM2M0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YjNjNCBcdWIwYThcdWM3OTBcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjIFx1YjQ1MCBcdWM3MjBcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAoXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHViMGE4XHVjNzkwLCBcdWM3OTFcdWM3NDAgXHViMGE4XHVjNzkwKSBcdWQwYTRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjI5NCBcdWM3N2NcdWM3NDQgXHVjNzdjXHVjNWI0XHViMDk4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwYTRcdWM2NDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1Yzc3NFx1YzEzMSBcdWM3MjBcdWQ2MTVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjZGE0XHVjNzQ0IFx1Y2Q5YyBcdWMzMGRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YzMwZFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjBhOFx1Yzc5MFx1Yzc1OCBcdWQwYTRcdWFjMDAgXHViYzAwXHViOWFjXHViYmY4XHVkMTMwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDBhNFx1YjI5NCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NzQgMTUwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAyNTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWMwYWNcdWI3OGNcdWM3NTggXHVkMGE0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMTJcdWM3NTggXHVjODA4XHViMzAwXHVhYzEyXHVjNzc0XHViMmU0LiBcdWQwYTRcdWFjMDAgXHVjNTkxXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3OTBcdWMyZTBcdWJjZjRcdWIyZTQgXHVkMGE0XHVhYzAwIFx1ZDA3MCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHViMGE4XHVjNzkwXHVjNzc0XHVhY2UwLCBcdWM3NGNcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1ZDBhNFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVjMGFjXHViNzhjXHVhY2ZjIFx1Y2RhNFx1Yzc0NCBcdWNkOTRcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1ZWNcdWM3OTBcdWM3NTggXHVkMGE0XHVhYzAwIFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMCBcdWIyZThcdWM3MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQwYTRcdWM3NTggXHViYzk0XHVjNzA0XHViMDk4IFx1Yzc1OFx1YmJmOCBcdWM1ZWRcdWMyZGMgXHViMGE4XHVjNzkwXHVjNjQwIFx1YjNkOVx1Yzc3Y1x1ZDU1OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMzBkXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBMRVMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBOIGJveXMgYW5kIE4gZ2lybHMgYXQgYSBkYW5jZSBwYXJ0eS4gV2UgaGF2ZSBtZWFzdXJlZCB0aGVpciBoZWlnaHRzLiBFYWNoIGJveSB3aWxsIG9ubHkgZGFuY2Ugd2l0aCBhIGdpcmwgYW5kIGVhY2ggZ2lybCB3aWxsIG9ubHkgZGFuY2Ugd2l0aCBhIGJveS4gRXZlcnlvbmUgd2lsbCBkYW5jZSB3aXRoIGF0IG1vc3Qgb25lIHBhcnRuZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggYm95IGVpdGhlciB3YW50cyB0byBkYW5jZSB3aXRoIGEgZ2lybCB3aG8gaXMgdGFsbGVyIHRoYW4gaGltIG9yIHdpdGggYSBnaXJsIHdobyBpcyBzaG9ydGVyIHRoYW4gaGltLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbmFsb2dvdXNseSwgZWFjaCBnaXJsIGVpdGhlciB3YW50cyB0byBkYW5jZSB3aXRoIGEgYm95IHdobyBpcyB0YWxsZXIgdGhhbiBoZXIgb3Igd2l0aCBhIGJveSB3aG8gaXMgc2hvcnRlciB0aGFuIGhlci4gQm95cyBhbmQgZ2lybHMgd2hvIGFyZSBlcXVhbGx5IHRhbGwgbmV2ZXIgd2FudCB0byBkYW5jZSB3aXRoIGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJlc3BlY3RpbmcgZXZlcnlvbmUmIzM5O3Mgd2lzaGVzLCBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGRhbmNpbmcgcGFpcnMgdGhhdCBjYW4gYmUgYWNoaWV2ZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBpbnRlZ2VycyB3aG9zZSBhYnNvbHV0ZSB2YWx1ZXMgYXJlIGJldHdlZW4gMTUwMCBhbmQgMjUwMCwgaW5jbHVzaXZlLiBUaGVpciBhYnNvbHV0ZSB2YWx1ZXMgcmVwcmVzZW50IHRoZSBoZWlnaHQgb2YgZWFjaCBvZiB0aGUgYm95cyBpbiBtaWxsaW1ldHJlcy4gUG9zaXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBib3lzIHdobyB3YW50IHRvIGRhbmNlIHdpdGggZ2lybHMgdGFsbGVyIHRoYW4gdGhlbXNlbHZlcywgd2hpbGUgbmVnYXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBib3lzIHdobyB3YW50IHRvIGRhbmNlIHdpdGggZ2lybHMgc2hvcnRlciB0aGFuIHRoZW1zZWx2ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgd2hvc2UgYWJzb2x1dGUgdmFsdWVzIGFyZSBiZXR3ZWVuIDE1MDAgYW5kIDI1MDAsIGluY2x1c2l2ZS4gVGhlaXIgYWJzb2x1dGUgdmFsdWVzIHJlcHJlc2VudCB0aGUgaGVpZ2h0IG9mIGVhY2ggb2YgdGhlIGdpcmxzIGluIG1pbGxpbWV0cmVzLiBQb3NpdGl2ZSBoZWlnaHQgdmFsdWVzIGluZGljYXRlIGdpcmxzIHdobyB3YW50IHRvIGRhbmNlIHdpdGggYm95cyB0YWxsZXIgdGhhbiB0aGVtc2VsdmVzLCB3aGlsZSBuZWdhdGl2ZSBoZWlnaHQgdmFsdWVzIGluZGljYXRlIGdpcmxzIHdobyB3YW50IHRvIGRhbmNlIHdpdGggYm95cyBzaG9ydGVyIHRoYW4gdGhlbXNlbHZlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltdW0gbnVtYmVyIG9mIGRhbmNpbmcgcGFpcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==