Dancing Elephants#2256
Dancing Elephants is a spectacular show in Pattaya featuring elephants performing in a single line, known as the stage.
After years of training, the elephants have mastered numerous dance moves. Each show consists of a sequence of acts, where, in each act, one elephant performs a dance move, potentially changing its position on the stage.
The show producers aim to create a photo album capturing the entire show. They plan to take pictures of all the elephants after each act.
At any point during the show, some elephants might be standing in the same position, meaning they are simply adjacent to each other.
A single camera can capture a group of elephants only if all their positions are within a segment of length (including both boundaries of the segment). Since elephants can be spread across the stage, several cameras might be needed to photograph all the elephants at once.
For example, suppose l = 10 and the elephants are at positions , , , and . At this moment, one camera is sufficient to photograph all the elephants, as shown below (elephants are shown as triangles, cameras as trapezoids).
In the next act, the elephant at position moves to position . After this, at least two cameras are required to capture all the elephants simultaneously.
In the next act, the elephant at position moves to position . In this case, cameras are needed to photograph all the elephants.
Your task is to determine the minimum number of cameras required to photograph all the elephants after each act.
The first line of the input contains three non-negative integers , , and (0 \leq n \leq 15 \cdot 10^4, 0 \leq l \leq 10^9, 0 \leq m \leq 15 \cdot 10^4).
The following lines each contain one integer x_i, representing the position of each elephant (0 \leq x_i \leq 10^9). All the initial positions are sorted. Note that during the dance, the order of the elephants may change.
The next lines each contain two integers and , indicating that in the corresponding act, the elephant numbered moves to a position with coordinate . It is guaranteed that satisfies the constraint 0 \leq y \leq 10^9.
Print lines, each containing the minimum number of cameras needed to photograph all the elephants after each act.
Example 1