시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 385 100 65 28.261%

문제

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

  • 모든 후보자는 오직 한 개의 포스터만을 벽에 붙일 수 있다.
  • 모든 포스터는 벽의 높이와 같게 하고, 포스터 너비는 자유다.
  • 벽은 조각으로 나누어져 있으며, 하나의 조각의 단위는 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+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4XHViNGU0XHVjNzQwIFx1YjEwOFx1YmU0NFx1YWMwMCAxMDAsMDAwLDAwMGJ5dGVcdWM3NTggXHViY2JkXHVjNzQ0IFx1YjljOFx1YjgyOFx1ZDU3NCBcdWM4ZmNcdWM1YzhcdWIyZTQuIFx1YzJkY1x1YzdhNSBcdWQ2YzRcdWJjZjQgXHVkNjRkXHViY2Y0XHVhYzAwIFx1YzJkY1x1Yzc5MVx1YjQxMFx1Yzc0NCBcdWI1NGMgXHVhYzAxIFx1ZDZjNFx1YmNmNFx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWJjYmRcdWM1ZDBcdWIyZTRcdWFjMDAgXHVhZGY4XHViNGU0XHVjNzU4IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yjk3YyBcdWJkOTlcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHViMmU0XHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWJkOTlcdWM3NzRcdWI4MjRcdWIyOTQgXHViZDgwXHViZDg0XHVjNWQwIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1YWMwMCBcdWM3ODhcdWM1YjRcdWIzYzQgXHVhZGY4IFx1YzcwNFx1YzVkMFx1YjJlNCBcdWJkOTlcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNmQ0XHViNGRjIFx1YjljOFx1Yzc0NFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWMxMjBcdWFjNzAgXHVjODA0XHViMGEwIFx1YmNiZFx1YzVkMCBcdWJhODcgXHViYTg1XHVjNzU4IFx1YzJkY1x1YzdhNSBcdWQzZWNcdWMyYTRcdWQxMzBcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NThcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4MTVcdWJjZjRcdWIzMDBcdWI4NWMgXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3OCBcdWQ2YzRcdWM1ZDAgXHVjMTIwXHVhYzcwIFx1YzgwNFx1YjBhMFx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjZDFkIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDNcL3BvdC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjVweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMFx1YjI5NCBcdWQzZWNcdWMyYTRcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4IG4oMSZsZTtuJmxlOzEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjIG5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHViMDVkXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMDVkXHVjNzU4IFx1YzcwNFx1Y2U1OCBsLCByXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBsICZsZTsmbmJzcDtyICZsZTsgMTAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHViNDFjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQzZWNcdWMyYTRcdWQxMzBcdWI5N2MgXHViZDk5XHVjNzc4IFx1ZDZjNFx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVkM2VjXHVjMmE0XHVkMTMwXHVjNzU4IFx1Y2QxZCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzNzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXlvcidzIHBvc3RlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjaXRpemVucyBvZiBCeXRldG93biwgQUIsIGNvdWxkIG5vdCBzdGFuZCB0aGF0IHRoZSBjYW5kaWRhdGVzIGluIHRoZSBtYXlvcmFsIGVsZWN0aW9uIGNhbXBhaWduIGhhdmUgYmVlbiBwbGFjaW5nIHRoZWlyIGVsZWN0b3JhbCBwb3N0ZXJzIGF0IGFsbCBwbGFjZXMgYXQgdGhlaXIgd2hpbS4gVGhlIGNpdHkgY291bmNpbCBoYXMgZmluYWxseSBkZWNpZGVkIHRvIGJ1aWxkIGFuIGVsZWN0b3JhbCB3YWxsIGZvciBwbGFjaW5nIHRoZSBwb3N0ZXJzIGFuZCBpbnRyb2R1Y2UgdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5FdmVyeSBjYW5kaWRhdGUgY2FuIHBsYWNlIGV4YWN0bHkgb25lIHBvc3RlciBvbiB0aGUgd2FsbC48XC9saT5cclxuXHQ8bGk+QWxsIHBvc3RlcnMgYXJlIG9mIHRoZSBzYW1lIGhlaWdodCBlcXVhbCB0byB0aGUgaGVpZ2h0IG9mIHRoZSB3YWxsOyB0aGUgd2lkdGggb2YgYSBwb3N0ZXIgY2FuIGJlIGFueSBpbnRlZ2VyIG51bWJlciBvZiBieXRlcyAoYnl0ZSBpcyB0aGUgdW5pdCBvZiBsZW5ndGggaW4gQnl0ZXRvd24pLjxcL2xpPlxyXG5cdDxsaT5UaGUgd2FsbCBpcyBkaXZpZGVkIGludG8gc2VnbWVudHMgYW5kIHRoZSB3aWR0aCBvZiBlYWNoIHNlZ21lbnQgaXMgb25lIGJ5dGUuPFwvbGk+XHJcblx0PGxpPkVhY2ggcG9zdGVyIG11c3QgY29tcGxldGVseSBjb3ZlciBhIGNvbnRpZ3VvdXMgbnVtYmVyIG9mIHdhbGwgc2VnbWVudHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhleSBoYXZlIGJ1aWx0IGEgd2FsbCAxMDAwMDAwMCBieXRlcyBsb25nIChzdWNoIHRoYXQgdGhlcmUgaXMgZW5vdWdoIHBsYWNlIGZvciBhbGwgY2FuZGlkYXRlcykuIFdoZW4gdGhlIGVsZWN0b3JhbCBjYW1wYWlnbiB3YXMgcmVzdGFydGVkLCB0aGUgY2FuZGlkYXRlcyB3ZXJlIHBsYWNpbmcgdGhlaXIgcG9zdGVycyBvbiB0aGUgd2FsbCBhbmQgdGhlaXIgcG9zdGVycyBkaWZmZXJlZCB3aWRlbHkgaW4gd2lkdGguIE1vcmVvdmVyLCB0aGUgY2FuZGlkYXRlcyBzdGFydGVkIHBsYWNpbmcgdGhlaXIgcG9zdGVycyBvbiB3YWxsIHNlZ21lbnRzIGFscmVhZHkgb2NjdXBpZWQgYnkgb3RoZXIgcG9zdGVycy4gRXZlcnlvbmUgaW4gQnl0ZXRvd24gd2FzIGN1cmlvdXMgd2hvc2UgcG9zdGVycyB3aWxsIGJlIHZpc2libGUgKGVudGlyZWx5IG9yIGluIHBhcnQpIG9uIHRoZSBsYXN0IGRheSBiZWZvcmUgZWxlY3Rpb25zLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gZmluZCB0aGUgbnVtYmVyIG9mIHZpc2libGUgcG9zdGVycyB3aGVuIGFsbCB0aGUgcG9zdGVycyBhcmUgcGxhY2VkIGdpdmVuIHRoZSBpbmZvcm1hdGlvbiBhYm91dCBwb3N0ZXJzJiMzOTsgc2l6ZSwgdGhlaXIgcGxhY2UgYW5kIG9yZGVyIG9mIHBsYWNlbWVudCBvbiB0aGUgZWxlY3RvcmFsIHdhbGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIG51bWJlciBjIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNhc2VzIHRoYXQgZm9sbG93LiBUaGUgZmlyc3QgbGluZSBvZiBkYXRhIGZvciBhIHNpbmdsZSBjYXNlIGNvbnRhaW5zIG51bWJlciAxICZsZTsgbiAmbGU7IDEwMDAwLiBUaGUgc3Vic2VxdWVudCBuIGxpbmVzIGRlc2NyaWJlIHRoZSBwb3N0ZXJzIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IHdlcmUgcGxhY2VkLiBUaGUgaS10aCBsaW5lIGFtb25nIHRoZSBuIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgbDxzdWI+aTxcL3N1Yj4gYW5kIHI8c3ViPmk8XC9zdWI+IHdoaWNoIGFyZSB0aGUgbnVtYmVyIG9mIHRoZSB3YWxsIHNlZ21lbnQgb2NjdXBpZWQgYnkgdGhlIGxlZnQgZW5kIGFuZCB0aGUgcmlnaHQgZW5kIG9mIHRoZSBpLXRoIHBvc3RlciwgcmVzcGVjdGl2ZWx5LiBXZSBrbm93IHRoYXQgZm9yIGVhY2ggMSAmbGU7IGkgJmxlOyBuLCAxICZsZTsgbDxzdWI+aTxcL3N1Yj4gJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwMDAwLiBBZnRlciB0aGUgaS10aCBwb3N0ZXIgaXMgcGxhY2VkLCBpdCBlbnRpcmVseSBjb3ZlcnMgYWxsIHdhbGwgc2VnbWVudHMgbnVtYmVyZWQgbDxzdWI+aTxcL3N1Yj4sIGw8c3ViPmk8XC9zdWI+KzEgLC4uLiAsIHI8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiIiLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wb3N0ZXJzLmpwZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0N3B4OyB3aWR0aDo1NTZweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d