시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2721259245.320%

문제

수직선상에 N(1 ≤ N ≤ 25,000)개의 구간이 있다. 구간의 양 끝점은 각각 정수 좌표 한 개로 나타내어진다. 구간은 겹칠 수 있고, 어떤 구간이 다른 구간을 완전히 포함할 수도 있지만, 모든 구간은 다른 구간과 서로 자신의 끝점을 공유하지 않는다. 하나의 위치는 최대 하나의 구간의 어떤 끝점만이 될 수 있다. 어떤 한 구간이 다른 구간들을 최대한 많이 포함하고 있는 개수를 찾으시오.

      *-----------*
      |           |
*-----------*
|           |
| *-*   *-* |
| | |   | | |
1 2 3 4 5 6 7 8 9 10

구간들의 배치가 위와 같은 경우, 답은 1-7구간이 포함하고 있는 다른 구간의 개수 2(2-3구간, 5-6구간)이다.

입력

첫째 줄에 N이 들어온다.

둘째 줄부터 N+1번째 줄까지 N개의 줄마다 각각 해당 구간을 나타내는 두 정수 A, B가 들어온다. (1 ≤ A < B ≤ 2,000,000,000)

출력

어떤 한 구간이 다른 구간들을 최대한 많이 포함하고 있는 개수를 출력하시오.

예제 입력 1

4
1 7
2 3
5 6
4 10

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIxMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVhZDZjXHVhYzA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM5YzFcdWMxMjBcdWMwYzFcdWM1ZDAgTigxICZsZTsmbmJzcDtOICZsZTsgMjUsMDAwKVx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkNmNcdWFjMDRcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHVjODE1XHVjMjE4IFx1Yzg4Y1x1ZDQ1YyBcdWQ1NWMgXHVhYzFjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzViNFx1YzljNFx1YjJlNC4gXHVhZDZjXHVhYzA0XHVjNzQwIFx1YWNiOVx1Y2U2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM1YjRcdWI1YTQgXHVhZDZjXHVhYzA0XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVjNjQ0XHVjODA0XHVkNzg4IFx1ZDNlY1x1ZDU2OFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWJhYThcdWI0ZTAgXHVhZDZjXHVhYzA0XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWFjMDRcdWFjZmMgXHVjMTFjXHViODVjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWIwNWRcdWM4MTBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM1YjRcdWI1YTQgXHViMDVkXHVjODEwXHViOWNjXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVkNTVjIFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVhZDZjXHVhYzA0XHViNGU0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjYzNlXHVjNzNjXHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgKi0tLS0tLS0tLS0tKlxyXG4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgfCZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyB8XHJcbiotLS0tLS0tLS0tLSpcclxufCZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyB8XHJcbnwgKi0qJm5ic3A7Jm5ic3A7ICotKiB8XHJcbnwgfCB8Jm5ic3A7Jm5ic3A7IHwgfCB8XHJcbjEgMiAzIDQgNSA2IDcgOCA5IDEwPFwvcHJlPlxyXG5cclxuPHA+XHVhZDZjXHVhYzA0XHViNGU0XHVjNzU4IFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMCwgXHViMmY1XHVjNzQwIDEtN1x1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWFjMDRcdWM3NTggXHVhYzFjXHVjMjE4IDIoMi0zXHVhZDZjXHVhYzA0LCA1LTZcdWFkNmNcdWFjMDQpXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHViOWM4XHViMmU0IFx1YWMwMVx1YWMwMSBcdWQ1NzRcdWIyZjkgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IEEsIEJcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiAoMSAmbGU7IEEgJmx0OyBCICZsZTsgMiwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1YjRcdWI1YTQgXHVkNTVjIFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVhZDZjXHVhYzA0XHViNGU0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NzQgXHVkM2VjXHVkNTY4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIxMDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSYWluIENvdmVyIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZmFybSBoYXMgc3VmZmVyZWQgYW4gZXh0cmFvcmRpbmFyeSBhbW91bnQgb2YgcmFpbiBsYXRlbHkuIE5vdyB3YW50aW5nIHRvIGVhdCBmcmVlIGZyb20gcmFpbiwgdGhlIGluZ2VuaW91cyBjb3dzIGhhdmUgc2V0IHVwIE4gKDEgJmx0Oz0gTiAmbHQ7PSAyNSwwMDApIHJlY3Rhbmd1bGFyIHVtYnJlbGxhcyB0byBzaGllbGQgdGhlbSBmcm9tIHRoZSByYWluIHdoaWxlIHRoZXkgYXJlIGdyYXppbmcuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzJiMzOTsgZmllbGQgaXMgYSBzaW5nbGUgc3RyaXAgb2YgZ3Jhc3MsIGFuZCBlYWNoIHVtYnJlbGxhIGNvbXBsZXRlbHkgY292ZXJzIHNvbWUgaW50ZXJ2YWwgb2YgZ3Jhc3MuIEhvd2V2ZXIsIHRoZXkgaGF2ZSBzZXQgdXAgdGhlIHVtYnJlbGxhcyBpbiBhIG1vc3QgaGFwaGF6YXJkIHdheSwgYW5kIHNvbWUgb2YgdGhlIHVtYnJlbGxhcyBjb3ZlciBhbGwgb3IgcGFydCBvZiBhbiBhcmVhIGNvdmVyZWQgYnkgb25lIG9yIG1vcmUgb3RoZXIgdW1icmVsbGFzLiBZb3VyIHRhc2sgaXMgdG8gZmluZCB0aGUgZ3JlYXRlc3QgbnVtYmVyIG9mIHVtYnJlbGxhcyB3aG9zZSBhcmVhcyBhcmUgY29tcGxldGVseSBjb3ZlcmVkIGJ5IGEgc2luZ2xlIHVtYnJlbGxhLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBzaW5nbGUgaW50ZWdlciBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgQSBhbmQgQiAoMSAmbHQ7PSBBICZsdDsgQiAmbHQ7PSAyLDAwMCwwMDAsMDAwKSB0aGF0IGFyZSB0aGUgZW5kcG9pbnRzIG9mIHRoZSBpbnRlcnZhbCBvZiBncmFzcyBjb3ZlcmVkIGJ5IGFuIHVtYnJlbGxhLiBObyBlbmRwb2ludCBpcyBzaGFyZWQgYnkgYW55IHR3byB1bWJyZWxsYXMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciB0aGF0IGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiB1bWJyZWxsYXMgd2hvc2UgY292ZXJhZ2UgaXMgZW50aXJlbHkgd2l0aGluIHRoZSBhcmVhIGNvdmVyZWQgYnkgYW5vdGhlciBzaW5nbGUgdW1icmVsbGEuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZpcnN0IHVtYnJlbGxhIGNvdmVycyB0aGUgc2Vjb25kIGFuZCB0aGlyZCB1bWJyZWxsYXMsIGFzIHNlZW4gYmVsb3c6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICotLS0tLS0tLS0tLSpcclxuICAgICAgfCAgICAgICAgICAgfFxyXG4qLS0tLS0tLS0tLS0qXHJcbnwgICAgICAgICAgIHxcclxufCAqLSogICAqLSogfFxyXG58IHwgfCAgIHwgfCB8XHJcbjEgMiAzIDQgNSA2IDcgOCA5IDEwXHJcbjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d