시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 945 391 277 46.712%

문제

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다.

상근이는 매일 매일 화단에 식물을 하나씩 심는다. 첫 번째 날에 심은 식물의 높이는 1이고, 그 다음날에 심은 식물은 전날에 심은 식물의 높이보다 1 크다.

새 식물의 줄기가 다른 식물의 수평 선분과 교차하는 경우가 있다. 이러한 경우에 그 위치에는 꽃이 하나 피게 된다. (이미 꽃이 있는 경우에는 꽃이 더 피지 않는다) 점에서 접하는 경우에는 꽃이 피지 않는다.

아래 그림은 예제를 나타낸 것이다.

모든 식물의 좌표가 주어졌을 때, 매일 매일 피는 꽃의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 식물을 심은 날의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 매일 매일 심은 식물의 두 줄기 좌표 L과 R이 주어진다. (1 ≤ L < R ≤ 100,000) 

출력

총 N개의 줄에 매일 매일 핀 꽃의 수를 출력한다.

예제 입력 1

4
1 4
3 7
1 6
2 6

예제 출력 1

0
1
1
2
W3sicHJvYmxlbV9pZCI6IjI5MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJMUkggXHVjMmRkXHViYjNjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzIwXHVjODA0XHVjNzkwIFx1Yzg3MFx1Yzc5MVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjOTA0XHVhZTMwIFx1YjQ1MCBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzJkZFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWMyZGRcdWJiM2NcdWM3NDAgXHVjOTA0XHVhZTMwXHVjNzU4IHhcdWM4OGNcdWQ0NWMgTCwgUlx1YWNmYyBcdWIxOTJcdWM3NzQgSFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBMPTIsIFI9NSwgSD00XHVjNzc4IFx1YzJkZFx1YmIzY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC82MzA4NTEyYS0xYzgyLTRhY2YtYWRmNC04MzU5MGM0NmRkNDNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwN3B4OyBoZWlnaHQ6IDE1MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWQ2NTRcdWIyZThcdWM1ZDAgXHVjMmRkXHViYjNjXHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMyZWNcdWIyOTRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViMGEwXHVjNWQwIFx1YzJlY1x1Yzc0MCBcdWMyZGRcdWJiM2NcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDFcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWIwYTBcdWM1ZDAgXHVjMmVjXHVjNzQwIFx1YzJkZFx1YmIzY1x1Yzc0MCBcdWM4MDRcdWIwYTBcdWM1ZDAgXHVjMmVjXHVjNzQwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWJjZjRcdWIyZTQgMSBcdWQwNmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjOCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjOTA0XHVhZTMwXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjMjE4XHVkM2M5IFx1YzEyMFx1YmQ4NFx1YWNmYyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFkZjggXHVjNzA0XHVjZTU4XHVjNWQwXHViMjk0IFx1YWY0M1x1Yzc3NCBcdWQ1NThcdWIwOTggXHVkNTNjXHVhYzhjIFx1YjQxY1x1YjJlNC4gKFx1Yzc3NFx1YmJmOCBcdWFmNDNcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFmNDNcdWM3NzQgXHViMzU0IFx1ZDUzY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpIFx1YzgxMFx1YzVkMFx1YzExYyBcdWM4MTFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWY0M1x1Yzc3NCBcdWQ1M2NcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2EyNzkxZWQxLTc4ZGEtNDRlNC05ZTczLWMwNDIyNjFkNWI4OVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogODQ0cHg7IGhlaWdodDogMTUwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVkNTNjXHViMjk0IFx1YWY0M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkZFx1YmIzY1x1Yzc0NCBcdWMyZWNcdWM3NDAgXHViMGEwXHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVjMmVjXHVjNzQwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWI0NTAgXHVjOTA0XHVhZTMwIFx1Yzg4Y1x1ZDQ1YyBMXHVhY2ZjIFJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEwgJmx0OyBSICZsZTsgMTAwLDAwMCkmbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWQ1NDAgXHVhZjQzXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNWSkVUSUNJIiwiZGVzY3JpcHRpb24iOiI8cD5PbiBhIGZhcmF3YXkgcGxhbmV0LCBzdHJhbmdlIHBsYW50cyB3aXRoIHR3byBzdGVtcyBjYW4gYmUgZm91bmQuIEV2ZXJ5IHBsYW50IG9uIHRoZSBwbGFuZXQgY2FuIGJlIGRlc2NyaWJlZCBieSB0aHJlZSBudW1iZXJzOiB0aGUgeC1jb29yZGluYXRlcyBvZiB0aGUgc3RlbXMgTCBhbmQgUiwgYW5kIHRoZSBoZWlnaHQgSCBhdCB3aGljaCB0aGUgc3RlbXMgYXJlIGNvbm5lY3QuIFRoZSBpbWFnZSBkZXBpY3RzIGEgcGxhbnQgd2l0aCBMPTIsIFI9NSBhbmQgSD00LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzMXB4OyB3aWR0aDoxODNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FdmVyeSBkYXkgYSBuZXcgcGxhbnQgZ3Jvd3Mgb24gdGhlIHBsYW5ldC4gVGhlIHBsYW50IHRoYXQgZ3Jvd3Mgb24gZGF5IDEgaXMgb2YgaGVpZ2h0IDEsIGFuZCBldmVyeSBzdWJzZXF1ZW50IHBsYW50IGlzIG9uZSBoaWdoZXIgdGhhbiB0aGUgcHJldmlvdXMgb25lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGVuIGEgc3RlbSBvZiBhIG5ldyBwbGFudCBpbnRlcnNlY3RzIHRoZSBob3Jpem9udGFsIHNlZ21lbnQgb2YgYW5vdGhlciBwbGFudCwgYSBzbWFsbCBmbG93ZXIgZ3Jvd3MgKGlmIG9uZSB3YXNuJiMzOTt0IHRoZXJlIGFscmVhZHkpLiBJZiBzZWdtZW50cyBtZXJlbHkgdG91Y2ggaW4gYSBwb2ludCwgYSBmbG93ZXIgd2lsbCBub3QgZ3JvdyB0aGVyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBpbWFnZXMgYXJlIGEgdmlzdWFsaXphdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZSBvbiB0aGUgbmV4dCBwYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BsMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzJweDsgd2lkdGg6NzE4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBjb29yZGluYXRlcyBvZiBhbGwgcGxhbnRzLCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgbmV3IGZsb3dlciBldmVyeSBkYXkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgZGF5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIEwgYW5kIFIgKDEgJmxlOyBMICZsdDsgUiAmbGU7IDEwMCAwMDApLCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHN0ZW1zIG9mIGEgcGxhbnQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE4gbGluZXMsIHRoZSBudW1iZXIgb2YgbmV3IGZsb3dlcnMgYWZ0ZXIgZWFjaCBwbGFudCBncm93cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=