문제
N마리의 코끼리가 무대에서 한 줄로 서서 춤을 추는 코끼리 쇼는 파타야에서는 매우 유명하다.
몇 년간의 훈련을 하고 난후 코끼리들은 이 쇼에서 춤을 출 수 있게 된다.
이 쇼는 일련의 동작으로 이루어지며.
각 동작에서는 정확히 한 코끼리만 다른 장소로 이동하며 귀여운 춤을 추는데 제자리에 있을 수도 있다.
쇼 제작자는 전체 쇼의 사진을 포함하는 사진첩을 제작하려 한다.
각 동작마다 모든 코끼리들의 사진을 찍으려고 한다.
쇼가 진행되는 동안 여러 마리의 코끼리들은 같은 장소에 있을 수 있다.
이 경우 같은 장소에 있는 코끼리들은 단순히 다른 코끼리의 뒤에 서 있게 된다.
하나의 카메라는 길이 L의 선분 상에 있는 코끼리들의 사진만 찍을 수 있다(양 끝점 포함).
코끼리들은 무대 전체에 흩어져 있을 수 있으므로,
모든 코끼리들에 대한 스냅사진을 동시에 찍기 위해서는 여러 대의 카메라가 필요할 수도 있다.
예를 들어, L=10이고 무대에서 코끼리들의 위치가 10, 15, 17, 20이라고 하자. 이 순간에는,
아래의 그림과 같이, 하나의 카메라로 모든 코끼리들의 사진을 찍을 수 있다.
(삼각형은 코끼리를 나타내고 사다리꼴은 카메라를 나타낸다.)
그 다음의 동작에서는 15에 있던 코끼리가 32의 위치로 춤추며 이동한다.
이 동작 후의 스냅 사진을 찍기 위해서는 적어도 두 대의 카메라가 필요하다.
그 다음의 동작에서 10에 있던 코끼리가 7의 위치로 이동한다.
이 경우에서는 모든 코끼리들의 사진을 찍기 위해서 세대의 카메라가 필요하다.
당신이 할 일은 각 코끼리들의 동작 후의 코끼리 사진을 찍기 위한 최소의 카메라 개수를 찾아야 한다.
매 동작마다 카메라의 수는 증가할 수도 있고, 감소할 수도 있으며, 변화가 없을 수도 있음에 주의하라.
[예제 설명]
N=4, L=10 이고, 초기 코끼리의 위치가 다음과 같은 경우를 고려해보자.
X = 10 15 17 20
먼저, 함수 init 은 위의 파라미터로 호출될 것이다.
그 후, 함수 update 는 각 동작마다 한번씩 호출될 것이다. 다음에 함수 호출의 예와 정확한 리턴 값들이 있다:
입력
입력의 첫 번째 줄에는 코끼리의 수 N(1≤N≤150,000), 하나의 카메라로 찍을 수 있는 선분의 길이 L(0≤L≤1,000,000,000)과 쇼에서 코끼리가 진행하는 동작의 수 M(1≤M≤150,000)이 들어온다.
두 번째 줄부터 N+1 번째 줄까지 각 코끼리의 처음 위치 K(0≤K≤1,000,000,000)가 오름차순으로 정렬되어 주어진다.
그 다음 N+2 번째 줄부터 N+M+1 번째 줄까지 M 번의 코끼리 동작에 대한 정보 j(1≤j≤M)가 주어지며, 각각의 줄에는 코끼리의 j 번째 동작을 나타내는 jx(0≤jx〈N), jy(0≤jy≤1,000,000,000)가 공백으로 구분하여 들어온다. (jx : 움직일 코끼리의 번호, jy : 동작 후 변경되는 코끼리의 위치 )
출력
출력은 M개의 줄로 이루러지며 각 줄에는 코끼리의 동작 후 필요한 카메라의 최소개수를 출력한다.
예제1
4105
10
15
17
20
216
125
335
038
20
1
2
2
2
3