5823번 - 코끼리 서브태스크

N 마리의 코끼리가 무대에서 한 줄로 서서 춤을 추는 코끼리 쇼는 파타야에서는 매우 유명하다.

몇 년간의 훈련 후, 코끼리들은 이 쇼에서 많은 놀랄만한 춤들을 출 수 있게 된다. 이 쇼는 일련의 동작으로 이루어짂다. 각 동작에서는, 정확히 한 코끼리만 다른 장소로 이동하는 귀여운 춤을 추는데, 제자리에 있을 수도 있다.

쇼 제작자는 전체 쇼의 사진을 포함하는 사진첩을 제작하려 한다. 각 동작마다, 관객들에게 보여지는 모든 코끼리들의 사진을 찍으려고 한다.

쇼가 진행되는 동안, 여러 마리의 코끼리들은 같은 장소에 있을 수 있다. 이 경우, 같은 장소에 있는 코끼리들은 단순히 다른 코끼리의 뒤에 서 있게 된다.

하나의 카메라는 길이 L 의 선분상에 있는 코끼리들의 사진만 찍을 수 있다(양 끝점 포함). 코끼리들은 무대 전체에 흩어져 있을 수 있으므로, 모든 코끼리들에 대한 동시의 스냅사진을 찍기 위해서는 여러 대의 카메라가 필요할 수도 있다

예를 들어, L=10 이고 무대에서 코끼리들의 위치가 10, 15, 17, 그리고 20 이라고 하자. 이 순간에는, 아래의 그림과 같이, 하나의 카메라로 모든 코끼리들의 사진을 찍을 수 있다. (삼각형은 코끼리를 나타내고; 사다리꼴은 카메라를 나타낸다.)

그 다음의 동작에서는, 15 에 있던 코끼리가 32 의 위치로 춤추며 이동한다. 이 동작 후의 스냅사진을 찍기 위해서는 적어도 두 대의 카메라가 필요하다.

그 다음의 동작에서 10 에 있던 코끼리가 7 의 위치로 이동한다. 이 경우에서는 모든 코끼리들의 사진을 찍기 위해서 세대의 카메라가 필요하다.

이 상호작용 태스크에서는, 각 코끼리들의 동작 후의 코끼리 사진을 찍기 위한 최소 수의 카메라를 찾아야 한다. 매 동작마다 카메라의 수는 증가할 수도 있고, 감소할 수도 있으며, 변화가 없을 수도 있음에 주의하라.

다음의 함수를 작성하라:

함수 init(N,L,X)은 다음의 파라미터를 갖는다:

• N – 코끼리의 수. 코끼리는 0 이상 N-1 이하의 번호로 나타낸다.
• L – 하나의 카메라로 찍을 수 있는 선분의 길이. L 은 정수이며, 0 ≤ L ≤ 1 000 000 000 이다.
• X – 코끼리들의 처음 위치를 나타내는 하나의 일차원 정수 배열. 0 ≤ i < N 에 대하여, 코끼리 i 의 초기위치는 X[i]이고, 정렬이 되어있다. 좀 더 정확하게 말하자면, 0 ≤ X[0] ≤ ... ≤ X[N-1] ≤ 1 000 000 000 이다. 코끼리들의 춤(동작) 후에 위치가 재 배열 될 수 있음에 주의하라.

이 함수는 모든 다른 호출 전에 단 한번만 호출되며 어떤 값도 리턴하지 않는다.

함수 update(i,y)는 다음의 파라미터를 갖는다:

• i – 현재의 동작에서 움직이는 코끼리의 번호.
• y – 현재의 동작 후 변경되는 코끼리 i 의 위치. y 는 정수이며, 0 ≤ y ≤ 1 000 000 000 이다. 

이 함수는 여러 번 호출될 수 있다. 각 호출은 (이전의 모든 동작 다음에 나타나는) 한번의 동작을 의미한다. 각 호출은 이 동작 후의 모든 코끼리들의 사진을 찍는데 필요한 카메라의 최소 수를 리턴하여야 한다.

첫째 줄에 N, L, M이 주어진다. 둘째 줄부터 N개 줄에는 X[i]가 주어진다.

다음 M개 줄에는 update롤 호출할 때 사용하는 파라미터 i와 y가 주어진다.

update함수를 호출할 때 마다 리턴값을 한 줄에 하나씩 출력한다.

• 정확히 N = 2 코끼리만 있다.
• 처음과 그 이후의 각 동작 후, 모든 코끼리들의 위치는 서로 다르다.
• 함수 update 는 최대 100 번 호출된다.

• 1 ≤ N ≤ 100.
• 처음과 그 이후의 각 동작 후, 모든 코끼리들의 위치는 서로 다르다.
• 함수 update 는 최대 100 번 호출된다.

• 1 ≤ N ≤ 50 000.
• 처음과 그 이후의 각 동작 후, 모든 코끼리들의 위치는 서로 다르다.
• 함수 update 는 최대 50 000 번 호출된다.

• 1 ≤ N ≤ 70 000.
• 여러 마리의 코끼리들이 같은 위치에 있을 수 있다.
• 함수 update 는 최대 70 000 번 호출된다.

• 1 ≤ N ≤ 150 000.
• 여러 마리의 코끼리들이 같은 위치에 있을 수 있다.
• 함수 update 는 최대 150 000 번 호출된다.