시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 192 MB126736326031.669%

문제

마을에서 시장 선거를 하려 한다. 그래서 특정한 곳에 포스터를 붙이려 하는데, 선거 관리 위원회에서 몇 가지 규칙을 정해 주었다.

  • 모든 후보자는 오직 한 개의 포스터만을 벽에 붙일 수 있다.
  • 모든 포스터는 벽의 높이와 같게 하고, 포스터 너비는 자유다.
  • 벽은 조각으로 나누어져 있으며, 하나의 조각의 단위는 byte다.
  • 각각의 포스터는 정해진 벽 부분에 빈틈없이 붙어야 한다.

그리고 그들은 너비가 100,000,000byte의 벽을 마련해 주었다. 시장 후보 홍보가 시작됐을 때 각 후보자들은 벽에다가 그들의 포스터를 붙일 수 있다. 게다가 이미 붙이려는 부분에 포스터가 있어도 그 위에다 붙일 수 있다. 월드 마을사람들은 선거 전날 벽에 몇 명의 시장 포스터가 붙어 있는지 궁금하다. 당신의 할 일은 주어진 정보대로 포스터를 붙인 후에 선거 전날에 보이는 총 포스터의 수를 출력하는 프로그램을 작성하여라. 

입력

첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l < r ≤ 100,000,000)

출력

입력된 순서대로 포스터를 붙인 후에 보이는 포스터의 총 수를 출력하여라.

예제 입력 1

5
1 4
2 6
8 10
3 4
7 10

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjIzNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWM3YTUgXHVjMTIwXHVhYzcwIFx1ZDNlY1x1YzJhNFx1ZDEzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzJkY1x1YzdhNSBcdWMxMjBcdWFjNzBcdWI5N2MgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWFjZjNcdWM1ZDAgXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3NFx1YjgyNCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YzEyMFx1YWM3MCBcdWFkMDBcdWI5YWMgXHVjNzA0XHVjNmQwXHVkNjhjXHVjNWQwXHVjMTFjIFx1YmE4NyBcdWFjMDBcdWM5YzAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzgxNVx1ZDU3NCBcdWM4ZmNcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1ZDZjNFx1YmNmNFx1Yzc5MFx1YjI5NCBcdWM2MjRcdWM5YzEgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWQzZWNcdWMyYTRcdWQxMzBcdWI5Y2NcdWM3NDQgXHViY2JkXHVjNWQwIFx1YmQ5OVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVkM2VjXHVjMmE0XHVkMTMwXHViMjk0IFx1YmNiZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHVhYzE5XHVhYzhjIFx1ZDU1OFx1YWNlMCwgXHVkM2VjXHVjMmE0XHVkMTMwIFx1YjEwOFx1YmU0NFx1YjI5NCBcdWM3OTBcdWM3MjBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmNiZFx1Yzc0MCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWIyZThcdWM3MDRcdWIyOTQgYnl0ZVx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1YjI5NCBcdWM4MTVcdWQ1NzRcdWM5YzQgXHViY2JkIFx1YmQ4MFx1YmQ4NFx1YzVkMCBcdWJlNDhcdWQyYzhcdWM1YzZcdWM3NzQgXHViZDk5XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViNGU0XHVjNzQwIFx1YjEwOFx1YmU0NFx1YWMwMCAxMDAsMDAwLDAwMGJ5dGVcdWM3NTggXHViY2JkXHVjNzQ0IFx1YjljOFx1YjgyOFx1ZDU3NCBcdWM4ZmNcdWM1YzhcdWIyZTQuIFx1YzJkY1x1YzdhNSBcdWQ2YzRcdWJjZjQgXHVkNjRkXHViY2Y0XHVhYzAwIFx1YzJkY1x1Yzc5MVx1YjQxMFx1Yzc0NCBcdWI1NGMgXHVhYzAxIFx1ZDZjNFx1YmNmNFx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWJjYmRcdWM1ZDBcdWIyZTRcdWFjMDAgXHVhZGY4XHViNGU0XHVjNzU4IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yjk3YyBcdWJkOTlcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHViMmU0XHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWJkOTlcdWM3NzRcdWI4MjRcdWIyOTQgXHViZDgwXHViZDg0XHVjNWQwIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1YWMwMCBcdWM3ODhcdWM1YjRcdWIzYzQgXHVhZGY4IFx1YzcwNFx1YzVkMFx1YjJlNCBcdWJkOTlcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNmQ0XHViNGRjIFx1YjljOFx1Yzc0NFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMxMjBcdWFjNzAgXHVjODA0XHViMGEwIFx1YmNiZFx1YzVkMCBcdWJhODcgXHViYTg1XHVjNzU4IFx1YzJkY1x1YzdhNSBcdWQzZWNcdWMyYTRcdWQxMzBcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NThcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4MTVcdWJjZjRcdWIzMDBcdWI4NWMgXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3OCBcdWQ2YzRcdWM1ZDAgXHVjMTIwXHVhYzcwIFx1YzgwNFx1YjBhMFx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjZDFkIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDNcL3BvdC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjVweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzZWNcdWMyYTRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IG4oMSAmbGU7IG4gJmxlOyAxMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQzZWNcdWMyYTRcdWQxMzBcdWM3NTggXHVjNjdjXHVjYWJkIFx1YjA1ZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjA1ZFx1Yzc1OCBcdWM3MDRcdWNlNTggbCwgclx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbCAmbHQ7Jm5ic3A7ciAmbGU7IDEwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YjQxYyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3OCBcdWQ2YzRcdWM1ZDAgXHViY2Y0XHVjNzc0XHViMjk0IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yzc1OCBcdWNkMWQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzcwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWF5b3IncyBwb3N0ZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY2l0aXplbnMgb2YgQnl0ZXRvd24sIEFCLCBjb3VsZCBub3Qgc3RhbmQgdGhhdCB0aGUgY2FuZGlkYXRlcyBpbiB0aGUgbWF5b3JhbCBlbGVjdGlvbiBjYW1wYWlnbiBoYXZlIGJlZW4gcGxhY2luZyB0aGVpciBlbGVjdG9yYWwgcG9zdGVycyBhdCBhbGwgcGxhY2VzIGF0IHRoZWlyIHdoaW0uIFRoZSBjaXR5IGNvdW5jaWwgaGFzIGZpbmFsbHkgZGVjaWRlZCB0byBidWlsZCBhbiBlbGVjdG9yYWwgd2FsbCBmb3IgcGxhY2luZyB0aGUgcG9zdGVycyBhbmQgaW50cm9kdWNlIHRoZSBmb2xsb3dpbmcgcnVsZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RXZlcnkgY2FuZGlkYXRlIGNhbiBwbGFjZSBleGFjdGx5IG9uZSBwb3N0ZXIgb24gdGhlIHdhbGwuPFwvbGk+XHJcblx0PGxpPkFsbCBwb3N0ZXJzIGFyZSBvZiB0aGUgc2FtZSBoZWlnaHQgZXF1YWwgdG8gdGhlIGhlaWdodCBvZiB0aGUgd2FsbDsgdGhlIHdpZHRoIG9mIGEgcG9zdGVyIGNhbiBiZSBhbnkgaW50ZWdlciBudW1iZXIgb2YgYnl0ZXMgKGJ5dGUgaXMgdGhlIHVuaXQgb2YgbGVuZ3RoIGluIEJ5dGV0b3duKS48XC9saT5cclxuXHQ8bGk+VGhlIHdhbGwgaXMgZGl2aWRlZCBpbnRvIHNlZ21lbnRzIGFuZCB0aGUgd2lkdGggb2YgZWFjaCBzZWdtZW50IGlzIG9uZSBieXRlLjxcL2xpPlxyXG5cdDxsaT5FYWNoIHBvc3RlciBtdXN0IGNvbXBsZXRlbHkgY292ZXIgYSBjb250aWd1b3VzIG51bWJlciBvZiB3YWxsIHNlZ21lbnRzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZXkgaGF2ZSBidWlsdCBhIHdhbGwgMTAwMDAwMDAgYnl0ZXMgbG9uZyAoc3VjaCB0aGF0IHRoZXJlIGlzIGVub3VnaCBwbGFjZSBmb3IgYWxsIGNhbmRpZGF0ZXMpLiBXaGVuIHRoZSBlbGVjdG9yYWwgY2FtcGFpZ24gd2FzIHJlc3RhcnRlZCwgdGhlIGNhbmRpZGF0ZXMgd2VyZSBwbGFjaW5nIHRoZWlyIHBvc3RlcnMgb24gdGhlIHdhbGwgYW5kIHRoZWlyIHBvc3RlcnMgZGlmZmVyZWQgd2lkZWx5IGluIHdpZHRoLiBNb3Jlb3ZlciwgdGhlIGNhbmRpZGF0ZXMgc3RhcnRlZCBwbGFjaW5nIHRoZWlyIHBvc3RlcnMgb24gd2FsbCBzZWdtZW50cyBhbHJlYWR5IG9jY3VwaWVkIGJ5IG90aGVyIHBvc3RlcnMuIEV2ZXJ5b25lIGluIEJ5dGV0b3duIHdhcyBjdXJpb3VzIHdob3NlIHBvc3RlcnMgd2lsbCBiZSB2aXNpYmxlIChlbnRpcmVseSBvciBpbiBwYXJ0KSBvbiB0aGUgbGFzdCBkYXkgYmVmb3JlIGVsZWN0aW9ucy48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgdGhlIG51bWJlciBvZiB2aXNpYmxlIHBvc3RlcnMgd2hlbiBhbGwgdGhlIHBvc3RlcnMgYXJlIHBsYWNlZCBnaXZlbiB0aGUgaW5mb3JtYXRpb24gYWJvdXQgcG9zdGVycyYjMzk7IHNpemUsIHRoZWlyIHBsYWNlIGFuZCBvcmRlciBvZiBwbGFjZW1lbnQgb24gdGhlIGVsZWN0b3JhbCB3YWxsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBudW1iZXIgYyBnaXZpbmcgdGhlIG51bWJlciBvZiBjYXNlcyB0aGF0IGZvbGxvdy4gVGhlIGZpcnN0IGxpbmUgb2YgZGF0YSBmb3IgYSBzaW5nbGUgY2FzZSBjb250YWlucyBudW1iZXIgMSAmbGU7IG4gJmxlOyAxMDAwMC4gVGhlIHN1YnNlcXVlbnQgbiBsaW5lcyBkZXNjcmliZSB0aGUgcG9zdGVycyBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSB3ZXJlIHBsYWNlZC4gVGhlIGktdGggbGluZSBhbW9uZyB0aGUgbiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlciBudW1iZXJzIGw8c3ViPmk8XC9zdWI+IGFuZCByPHN1Yj5pPFwvc3ViPiB3aGljaCBhcmUgdGhlIG51bWJlciBvZiB0aGUgd2FsbCBzZWdtZW50IG9jY3VwaWVkIGJ5IHRoZSBsZWZ0IGVuZCBhbmQgdGhlIHJpZ2h0IGVuZCBvZiB0aGUgaS10aCBwb3N0ZXIsIHJlc3BlY3RpdmVseS4gV2Uga25vdyB0aGF0IGZvciBlYWNoIDEgJmxlOyBpICZsZTsgbiwgMSAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsdDsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwMDAwMC4gQWZ0ZXIgdGhlIGktdGggcG9zdGVyIGlzIHBsYWNlZCwgaXQgZW50aXJlbHkgY292ZXJzIGFsbCB3YWxsIHNlZ21lbnRzIG51bWJlcmVkIGw8c3ViPmk8XC9zdWI+LCBsPHN1Yj5pPFwvc3ViPisxICwuLi4gLCByPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcG9zdGVycy5qcGdcIiBzdHlsZT1cImhlaWdodDoyNDdweDsgd2lkdGg6NTU2cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=