시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 689 271 174 45.789%

문제

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 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
W3sicHJvYmxlbV9pZCI6IjI5MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJMUkggXHVjMmRkXHViYjNjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzIwXHVjODA0XHVjNzkwIFx1Yzg3MFx1Yzc5MVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjOTA0XHVhZTMwIFx1YjQ1MCBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzJkZFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWMyZGRcdWJiM2NcdWM3NDAgXHVjOTA0XHVhZTMwXHVjNzU4IHhcdWM4OGNcdWQ0NWMgTCwgUlx1YWNmYyBcdWIxOTJcdWM3NzQgSFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBMPTIsIFI9NSwgSD00XHVjNzc4IFx1YzJkZFx1YmIzY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzFweDsgd2lkdGg6MTgzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVkNjU0XHViMmU4XHVjNWQwIFx1YzJkZFx1YmIzY1x1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMmVjXHViMjk0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjBhMFx1YzVkMCBcdWMyZWNcdWM3NDAgXHVjMmRkXHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCAxXHVjNzc0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjXHViMGEwXHVjNWQwIFx1YzJlY1x1Yzc0MCBcdWMyZGRcdWJiM2NcdWM3NDAgXHVjODA0XHViMGEwXHVjNWQwIFx1YzJlY1x1Yzc0MCBcdWMyZGRcdWJiM2NcdWM3NTggXHViMTkyXHVjNzc0XHViY2Y0XHViMmU0IDEgXHVkMDZjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzggXHVjMmRkXHViYjNjXHVjNzU4IFx1YzkwNFx1YWUzMFx1YWMwMCBcdWIyZTRcdWI5NzggXHVjMmRkXHViYjNjXHVjNzU4IFx1YzIxOFx1ZDNjOSBcdWMxMjBcdWJkODRcdWFjZmMgXHVhZDUwXHVjYzI4XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVhZGY4IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YjI5NCBcdWFmNDNcdWM3NzQgXHVkNTU4XHViMDk4IFx1ZDUzY1x1YWM4YyBcdWI0MWNcdWIyZTQuIChcdWM3NzRcdWJiZjggXHVhZjQzXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZjQzXHVjNzc0IFx1YjM1NCBcdWQ1M2NcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KSBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjODExXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFmNDNcdWM3NzQgXHVkNTNjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wbDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMycHg7IHdpZHRoOjcxOHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMyZGRcdWJiM2NcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVkNTNjXHViMjk0IFx1YWY0M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJkZFx1YmIzY1x1Yzc0NCBcdWMyZWNcdWM3NDAgXHViMGEwXHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVjMmVjXHVjNzQwIFx1YzJkZFx1YmIzY1x1Yzc1OCBcdWI0NTAgXHVjOTA0XHVhZTMwIFx1Yzg4Y1x1ZDQ1YyBMXHVhY2ZjIFJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEwgJmx0OyBSICZsZTsgMTAwLDAwMCkmbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWQ1NDAgXHVhZjQzXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNWSkVUSUNJIiwiZGVzY3JpcHRpb24iOiI8cD5PbiBhIGZhcmF3YXkgcGxhbmV0LCBzdHJhbmdlIHBsYW50cyB3aXRoIHR3byBzdGVtcyBjYW4gYmUgZm91bmQuIEV2ZXJ5IHBsYW50IG9uIHRoZSBwbGFuZXQgY2FuIGJlIGRlc2NyaWJlZCBieSB0aHJlZSBudW1iZXJzOiB0aGUgeC1jb29yZGluYXRlcyBvZiB0aGUgc3RlbXMgTCBhbmQgUiwgYW5kIHRoZSBoZWlnaHQgSCBhdCB3aGljaCB0aGUgc3RlbXMgYXJlIGNvbm5lY3QuIFRoZSBpbWFnZSBkZXBpY3RzIGEgcGxhbnQgd2l0aCBMPTIsIFI9NSBhbmQgSD00LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzMXB4OyB3aWR0aDoxODNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FdmVyeSBkYXkgYSBuZXcgcGxhbnQgZ3Jvd3Mgb24gdGhlIHBsYW5ldC4gVGhlIHBsYW50IHRoYXQgZ3Jvd3Mgb24gZGF5IDEgaXMgb2YgaGVpZ2h0IDEsIGFuZCBldmVyeSBzdWJzZXF1ZW50IHBsYW50IGlzIG9uZSBoaWdoZXIgdGhhbiB0aGUgcHJldmlvdXMgb25lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGVuIGEgc3RlbSBvZiBhIG5ldyBwbGFudCBpbnRlcnNlY3RzIHRoZSBob3Jpem9udGFsIHNlZ21lbnQgb2YgYW5vdGhlciBwbGFudCwgYSBzbWFsbCBmbG93ZXIgZ3Jvd3MgKGlmIG9uZSB3YXNuJiMzOTt0IHRoZXJlIGFscmVhZHkpLiBJZiBzZWdtZW50cyBtZXJlbHkgdG91Y2ggaW4gYSBwb2ludCwgYSBmbG93ZXIgd2lsbCBub3QgZ3JvdyB0aGVyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBpbWFnZXMgYXJlIGEgdmlzdWFsaXphdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZSBvbiB0aGUgbmV4dCBwYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BsMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzJweDsgd2lkdGg6NzE4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHRoZSBjb29yZGluYXRlcyBvZiBhbGwgcGxhbnRzLCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2YgbmV3IGZsb3dlciBldmVyeSBkYXkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgZGF5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIEwgYW5kIFIgKDEgJmxlOyBMICZsdDsgUiAmbGU7IDEwMCAwMDApLCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHN0ZW1zIG9mIGEgcGxhbnQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE4gbGluZXMsIHRoZSBudW1iZXIgb2YgbmV3IGZsb3dlcnMgYWZ0ZXIgZWFjaCBwbGFudCBncm93cy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=