시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 166 59 57 38.255%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

2
-1800 -2200
1900 1700

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjI4MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDRcdWMyYTQgXHVkMzBjXHVkMmYwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIwYThcdWM3OTAgTlx1YmE4NVx1YWNmYyBcdWM1ZWNcdWM3OTAgTlx1YmE4NVx1Yzc3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOGZjXHVjZDVjXHVkNTVjIFx1YjMwNFx1YzJhNCBcdWQzMGNcdWQyZjBcdWM1ZDAgXHVjNjU0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViMGE4XHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5YyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM1ZWNcdWM3OTBcdWIyOTQgXHViMGE4XHVjNzkwXHVjNjQwIFx1Y2RhNFx1Yzc0NCBcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWNkYTRcdWM3NDQgXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWIwYThcdWM3OTBcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM1ZWNcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWIwYThcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YzVlY1x1Yzc5MFx1YjI5NCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YzcyMFx1ZDYxNVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1ZDU1YyBcdWM3MjBcdWQ2MTVcdWM3NDAgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHVjNWVjXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjNzIwXHVkNjE1XHVjNzQwIFx1Yzc5MFx1YzJlMFx1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzcyMFx1ZDYxNVx1Yzc3NFx1YjJlNC4gXHVjNWVjXHVjNzkwXHViM2M0IFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTBcdWM2NDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1YjNjNCBcdWIwYThcdWM3OTBcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjIFx1YjQ1MCBcdWM3MjBcdWQ2MTVcdWM3NzQgXHVjNzg4XHViMmU0LiAoXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHViMGE4XHVjNzkwLCBcdWM3OTFcdWM3NDAgXHViMGE4XHVjNzkwKSBcdWQwYTRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWM1ZWNcdWM3OTBcdWFjMDAgXHVjZGE0XHVjNzQ0IFx1Y2Q5NFx1YjI5NCBcdWM3N2NcdWM3NDQgXHVjNzdjXHVjNWI0XHViMDk4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHVkMGE0XHVjNjQwIFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWMxMzEgXHVjNzIwXHVkNjE1XHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Y2RhNFx1Yzc0NCBcdWNkOWMgXHVjMzBkXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWMzMGRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwYThcdWM3OTBcdWM3NTggXHVkMGE0XHVhYzAwIFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMCBcdWIyZThcdWM3MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQwYTRcdWIyOTQgXHVjODA4XHViMzAwXHVhYzEyXHVjNzc0IDE1MDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjUwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjMGFjXHViNzhjXHVjNzU4IFx1ZDBhNFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMwMFx1YWMxMlx1Yzc3NFx1YjJlNC4gXHVkMGE0XHVhYzAwIFx1YzU5MVx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjMmUwXHViY2Y0XHViMmU0IFx1ZDBhNFx1YWMwMCBcdWQwNzAgXHVjNWVjXHVjNzkwXHVjNjQwIFx1Y2RhNFx1Yzc0NCBcdWNkOTRcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjBhOFx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHVjNzRjXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQwYTRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWNkYTRcdWM3NDQgXHVjZDk0XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIwYThcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWVjXHVjNzkwXHVjNzU4IFx1ZDBhNFx1YWMwMCBcdWJjMDBcdWI5YWNcdWJiZjhcdWQxMzAgXHViMmU4XHVjNzA0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMGE0XHVjNzU4IFx1YmM5NFx1YzcwNFx1YjA5OCBcdWM3NThcdWJiZjggXHVjNWVkXHVjMmRjIFx1YjBhOFx1Yzc5MFx1YzY0MCBcdWIzZDlcdWM3N2NcdWQ1NThcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0XHVjNWI0IFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzMwZFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQTEVTIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBib3lzIGFuZCBOIGdpcmxzIGF0IGEgZGFuY2UgcGFydHkuIFdlIGhhdmUgbWVhc3VyZWQgdGhlaXIgaGVpZ2h0cy4gRWFjaCBib3kgd2lsbCBvbmx5IGRhbmNlIHdpdGggYSBnaXJsIGFuZCBlYWNoIGdpcmwgd2lsbCBvbmx5IGRhbmNlIHdpdGggYSBib3kuIEV2ZXJ5b25lIHdpbGwgZGFuY2Ugd2l0aCBhdCBtb3N0IG9uZSBwYXJ0bmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGJveSBlaXRoZXIgd2FudHMgdG8gZGFuY2Ugd2l0aCBhIGdpcmwgd2hvIGlzIHRhbGxlciB0aGFuIGhpbSBvciB3aXRoIGEgZ2lybCB3aG8gaXMgc2hvcnRlciB0aGFuIGhpbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QW5hbG9nb3VzbHksIGVhY2ggZ2lybCBlaXRoZXIgd2FudHMgdG8gZGFuY2Ugd2l0aCBhIGJveSB3aG8gaXMgdGFsbGVyIHRoYW4gaGVyIG9yIHdpdGggYSBib3kgd2hvIGlzIHNob3J0ZXIgdGhhbiBoZXIuIEJveXMgYW5kIGdpcmxzIHdobyBhcmUgZXF1YWxseSB0YWxsIG5ldmVyIHdhbnQgdG8gZGFuY2Ugd2l0aCBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZXNwZWN0aW5nIGV2ZXJ5b25lJiMzOTtzIHdpc2hlcywgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiBkYW5jaW5nIHBhaXJzIHRoYXQgY2FuIGJlIGFjaGlldmVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgd2hvc2UgYWJzb2x1dGUgdmFsdWVzIGFyZSBiZXR3ZWVuIDE1MDAgYW5kIDI1MDAsIGluY2x1c2l2ZS4gVGhlaXIgYWJzb2x1dGUgdmFsdWVzIHJlcHJlc2VudCB0aGUgaGVpZ2h0IG9mIGVhY2ggb2YgdGhlIGJveXMgaW4gbWlsbGltZXRyZXMuIFBvc2l0aXZlIGhlaWdodCB2YWx1ZXMgaW5kaWNhdGUgYm95cyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGdpcmxzIHRhbGxlciB0aGFuIHRoZW1zZWx2ZXMsIHdoaWxlIG5lZ2F0aXZlIGhlaWdodCB2YWx1ZXMgaW5kaWNhdGUgYm95cyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGdpcmxzIHNob3J0ZXIgdGhhbiB0aGVtc2VsdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGludGVnZXJzIHdob3NlIGFic29sdXRlIHZhbHVlcyBhcmUgYmV0d2VlbiAxNTAwIGFuZCAyNTAwLCBpbmNsdXNpdmUuIFRoZWlyIGFic29sdXRlIHZhbHVlcyByZXByZXNlbnQgdGhlIGhlaWdodCBvZiBlYWNoIG9mIHRoZSBnaXJscyBpbiBtaWxsaW1ldHJlcy4gUG9zaXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBnaXJscyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGJveXMgdGFsbGVyIHRoYW4gdGhlbXNlbHZlcywgd2hpbGUgbmVnYXRpdmUgaGVpZ2h0IHZhbHVlcyBpbmRpY2F0ZSBnaXJscyB3aG8gd2FudCB0byBkYW5jZSB3aXRoIGJveXMgc2hvcnRlciB0aGFuIHRoZW1zZWx2ZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtYXhpbXVtIG51bWJlciBvZiBkYW5jaW5nIHBhaXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=