시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 342 81 59 28.365%

문제

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

  • 모든 후보자는 오직 한 개의 포스터만을 벽에 붙일 수 있다.
  • 모든 포스터는 벽의 높이와 같게 하고, 포스터 너비는 자유다.
  • 벽은 조각으로 나누어져 있으며, 하나의 조각의 단위는 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+XHViOWM4XHVjNzQ0XHVjNWQwXHVjMTFjIFx1YzJkY1x1YzdhNSBcdWMxMjBcdWFjNzBcdWI5N2MgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDJiOVx1YzgxNVx1ZDU1YyBcdWFjZjNcdWM1ZDAgXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3NFx1YjgyNCBcdWQ1NThcdWIyOTRcdWIzNzAsIFx1YzEyMFx1YWM3MCBcdWFkMDBcdWI5YWMgXHVjNzA0XHVjNmQwXHVkNjhjXHVjNWQwXHVjMTFjIFx1YmE4N1x1YWMwMFx1YzljMCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjODE1XHVkNTc0IFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVkNmM0XHViY2Y0XHVjNzkwXHViMjk0IFx1YzYyNFx1YzljMSBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1YjljY1x1Yzc0NCBcdWJjYmRcdWM1ZDAgXHViZDk5XHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWQzZWNcdWMyYTRcdWQxMzBcdWIyOTQgXHViY2JkXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWFjOGMgXHVkNTU4XHVhY2UwLCBcdWQzZWNcdWMyYTRcdWQxMzAgXHViMTA4XHViZTQ0XHViMjk0IFx1Yzc5MFx1YzcyMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViY2JkXHVjNzQwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODcwXHVhYzAxXHVjNzU4IFx1YjJlOFx1YzcwNFx1YjI5NCBieXRlXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMDFcdWFjMDFcdWM3NTggXHVkM2VjXHVjMmE0XHVkMTMwXHViMjk0IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWJjYmQgXHViZDgwXHViZDg0XHVjNWQwIFx1YmU0OFx1ZDJjOFx1YzVjNlx1Yzc3NCBcdWJkOTlcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHViMTA4XHViZTQ0XHVhYzAwIDEwMCwwMDAsMDAwYnl0ZVx1Yzc1OCBcdWJjYmRcdWM3NDQgXHViOWM4XHViODI4XHVkNTc0IFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjMmRjXHVjN2E1IFx1ZDZjNFx1YmNmNCBcdWQ2NGRcdWJjZjRcdWFjMDAgXHVjMmRjXHVjNzkxXHViNDEwXHVjNzQ0IFx1YjU0YyBcdWFjMDEgXHVkNmM0XHViY2Y0XHVjNzkwXHViNGU0XHVjNzQwIFx1YmNiZFx1YzVkMFx1YjJlNFx1YWMwMCBcdWFkZjhcdWI0ZTRcdWM3NTggXHVkM2VjXHVjMmE0XHVkMTMwXHViOTdjIFx1YmQ5OVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjOGNcdWIyZTRcdWFjMDAgXHVjNzc0XHViYmY4IFx1YmQ5OVx1Yzc3NFx1YjgyNFx1YjI5NCBcdWJkODBcdWJkODRcdWM1ZDAgXHVkM2VjXHVjMmE0XHVkMTMwXHVhYzAwIFx1Yzc4OFx1YzViNFx1YjNjNCBcdWFkZjggXHVjNzA0XHVjNWQwXHViMmU0IFx1YmQ5OVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2ZDRcdWI0ZGMgXHViOWM4XHVjNzQ0XHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YzEyMFx1YWM3MCBcdWM4MDRcdWIwYTAgXHViY2JkXHVjNWQwIFx1YmE4NyBcdWJhODVcdWM3NTggXHVjMmRjXHVjN2E1IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU1OFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzU4IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxNVx1YmNmNFx1YjMwMFx1Yjg1YyBcdWQzZWNcdWMyYTRcdWQxMzBcdWI5N2MgXHViZDk5XHVjNzc4IFx1ZDZjNFx1YzVkMCBcdWMxMjBcdWFjNzAgXHVjODA0XHViMGEwXHVjNWQwIFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWNkMWQgXHVkM2VjXHVjMmE0XHVkMTMwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwM1wvcG90LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyNXB4OyB3aWR0aDo1MDZweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxJmxlO24mbGU7MTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkM2VjXHVjMmE0XHVkMTMwXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWIwNWRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWIwNWRcdWM3NTggXHVjNzA0XHVjZTU4IGwsIHJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGwsIHIgJmxlOyAxMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWI0MWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDNlY1x1YzJhNFx1ZDEzMFx1Yjk3YyBcdWJkOTlcdWM3NzggXHVkNmM0XHVjNWQwIFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWQzZWNcdWMyYTRcdWQxMzBcdWM3NTggXHVjZDFkIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1heW9yJ3MgcG9zdGVycyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNpdGl6ZW5zIG9mIEJ5dGV0b3duLCBBQiwgY291bGQgbm90IHN0YW5kIHRoYXQgdGhlIGNhbmRpZGF0ZXMgaW4gdGhlIG1heW9yYWwgZWxlY3Rpb24gY2FtcGFpZ24gaGF2ZSBiZWVuIHBsYWNpbmcgdGhlaXIgZWxlY3RvcmFsIHBvc3RlcnMgYXQgYWxsIHBsYWNlcyBhdCB0aGVpciB3aGltLiBUaGUgY2l0eSBjb3VuY2lsIGhhcyBmaW5hbGx5IGRlY2lkZWQgdG8gYnVpbGQgYW4gZWxlY3RvcmFsIHdhbGwgZm9yIHBsYWNpbmcgdGhlIHBvc3RlcnMgYW5kIGludHJvZHVjZSB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkV2ZXJ5IGNhbmRpZGF0ZSBjYW4gcGxhY2UgZXhhY3RseSBvbmUgcG9zdGVyIG9uIHRoZSB3YWxsLjxcL2xpPlxyXG5cdDxsaT5BbGwgcG9zdGVycyBhcmUgb2YgdGhlIHNhbWUgaGVpZ2h0IGVxdWFsIHRvIHRoZSBoZWlnaHQgb2YgdGhlIHdhbGw7IHRoZSB3aWR0aCBvZiBhIHBvc3RlciBjYW4gYmUgYW55IGludGVnZXIgbnVtYmVyIG9mIGJ5dGVzIChieXRlIGlzIHRoZSB1bml0IG9mIGxlbmd0aCBpbiBCeXRldG93bikuPFwvbGk+XHJcblx0PGxpPlRoZSB3YWxsIGlzIGRpdmlkZWQgaW50byBzZWdtZW50cyBhbmQgdGhlIHdpZHRoIG9mIGVhY2ggc2VnbWVudCBpcyBvbmUgYnl0ZS48XC9saT5cclxuXHQ8bGk+RWFjaCBwb3N0ZXIgbXVzdCBjb21wbGV0ZWx5IGNvdmVyIGEgY29udGlndW91cyBudW1iZXIgb2Ygd2FsbCBzZWdtZW50cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGV5IGhhdmUgYnVpbHQgYSB3YWxsIDEwMDAwMDAwIGJ5dGVzIGxvbmcgKHN1Y2ggdGhhdCB0aGVyZSBpcyBlbm91Z2ggcGxhY2UgZm9yIGFsbCBjYW5kaWRhdGVzKS4gV2hlbiB0aGUgZWxlY3RvcmFsIGNhbXBhaWduIHdhcyByZXN0YXJ0ZWQsIHRoZSBjYW5kaWRhdGVzIHdlcmUgcGxhY2luZyB0aGVpciBwb3N0ZXJzIG9uIHRoZSB3YWxsIGFuZCB0aGVpciBwb3N0ZXJzIGRpZmZlcmVkIHdpZGVseSBpbiB3aWR0aC4gTW9yZW92ZXIsIHRoZSBjYW5kaWRhdGVzIHN0YXJ0ZWQgcGxhY2luZyB0aGVpciBwb3N0ZXJzIG9uIHdhbGwgc2VnbWVudHMgYWxyZWFkeSBvY2N1cGllZCBieSBvdGhlciBwb3N0ZXJzLiBFdmVyeW9uZSBpbiBCeXRldG93biB3YXMgY3VyaW91cyB3aG9zZSBwb3N0ZXJzIHdpbGwgYmUgdmlzaWJsZSAoZW50aXJlbHkgb3IgaW4gcGFydCkgb24gdGhlIGxhc3QgZGF5IGJlZm9yZSBlbGVjdGlvbnMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBudW1iZXIgb2YgdmlzaWJsZSBwb3N0ZXJzIHdoZW4gYWxsIHRoZSBwb3N0ZXJzIGFyZSBwbGFjZWQgZ2l2ZW4gdGhlIGluZm9ybWF0aW9uIGFib3V0IHBvc3RlcnMmIzM5OyBzaXplLCB0aGVpciBwbGFjZSBhbmQgb3JkZXIgb2YgcGxhY2VtZW50IG9uIHRoZSBlbGVjdG9yYWwgd2FsbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgbnVtYmVyIGMgZ2l2aW5nIHRoZSBudW1iZXIgb2YgY2FzZXMgdGhhdCBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIG9mIGRhdGEgZm9yIGEgc2luZ2xlIGNhc2UgY29udGFpbnMgbnVtYmVyIDEgJmxlOyBuICZsZTsgMTAwMDAuIFRoZSBzdWJzZXF1ZW50IG4gbGluZXMgZGVzY3JpYmUgdGhlIHBvc3RlcnMgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgd2VyZSBwbGFjZWQuIFRoZSBpLXRoIGxpbmUgYW1vbmcgdGhlIG4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBsPHN1Yj5pPFwvc3ViPiBhbmQgcjxzdWI+aTxcL3N1Yj4gd2hpY2ggYXJlIHRoZSBudW1iZXIgb2YgdGhlIHdhbGwgc2VnbWVudCBvY2N1cGllZCBieSB0aGUgbGVmdCBlbmQgYW5kIHRoZSByaWdodCBlbmQgb2YgdGhlIGktdGggcG9zdGVyLCByZXNwZWN0aXZlbHkuIFdlIGtub3cgdGhhdCBmb3IgZWFjaCAxICZsZTsgaSAmbGU7IG4sIDEgJmxlOyBsPHN1Yj5pPFwvc3ViPiAmbGU7IHI8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMDAwMDAuIEFmdGVyIHRoZSBpLXRoIHBvc3RlciBpcyBwbGFjZWQsIGl0IGVudGlyZWx5IGNvdmVycyBhbGwgd2FsbCBzZWdtZW50cyBudW1iZXJlZCBsPHN1Yj5pPFwvc3ViPiwgbDxzdWI+aTxcL3N1Yj4rMSAsLi4uICwgcjxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Bvc3RlcnMuanBnXCIgc3R5bGU9XCJoZWlnaHQ6MjQ3cHg7IHdpZHRoOjU1NnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=