LRH 식물
시간 제한1초메모리 제한128 MB
매일 높이가 1씩 커지는 식물을 심을 때, 새 식물의 줄기가 이전 식물의 가로선과 교차하는 지점(중복 제외)의 개수를 날마다 계산합니다.
문제
한 정원사는 줄기 두 개와 수평 선분 하나로 이루어진 식물을 만들었다. 이 식물은 두 줄기의 x좌표 L, R과 높이 H로 나타낸다. 아래 그림은 L = 2, R = 5, H = 4인 식물이다.
정원사는 매일 화단에 식물을 하나씩 심는다. 첫째 날에 심는 식물의 높이는 1이고, 이후에 심는 식물은 전날에 심은 식물보다 높이가 1 크다.
새로 심은 식물의 줄기가 다른 식물의 수평 선분과 교차하면 그 점에 꽃이 하나 핀다. 이미 그 점에 꽃이 피어 있다면 꽃이 추가로 피지 않는다. 두 선분이 끝점에서만 닿는 경우에도 꽃이 피지 않는다.
다음 그림은 한 배치를 보여준다.
식물들의 좌표가 심는 순서대로 주어질 때, 매일 피는 꽃의 개수를 구하시오.
입력
첫째 줄에 식물을 심는 날의 수 N (1 <= N <= 100000)이 주어진다.
다음 N개 줄에는 그날 심는 식물의 두 줄기 x좌표 L, R이 주어진다 (1 <= L < R <= 100000).
출력
총 N개의 줄을 출력한다. i번째 줄에는 i번째 날에 핀 꽃의 수를 출력한다.