Raider Choragi and Queries (Easy)

Choragi is an elite agent tasked with raiding Wontagon, a secret national defense base of Korea. Wontagon is shaped like a donut and is divided into N zones as shown below. (The numbers in the figure are the zone numbers.)

Choragi deployed special squads, captured every zone, and took the enemies prisoner. The special squads are placed in the zones of Wontagon under the following conditions to manage the prisoners.

1. A special squad can be placed in one zone or in two mutually adjacent zones. (Two zones are adjacent if they share a boundary. In the figure above, zone 1 is adjacent to zone 2 and zone N.)
2. The number of prisoners managed by one special squad must be less than or equal to W.

Choragi knows how many prisoners there are in each zone. However, since some prisoners are transferred elsewhere and some enemies are caught after arriving as reinforcements and become new prisoners, the prisoner count in each zone keeps changing, and the situation has reached a level Choragi can no longer manage. Because Choragi does not have many special squads, he wants to place as few squads as possible. Over Q updates, where the prisoner count of one zone changes at a time, find the minimum number of special squads needed for Choragi in real time.

The first line contains the integers N, Q, and W, separated by spaces. (2 ≤ N ≤ 250 000, 1 ≤ Q ≤ 250 000, 1 ≤ W ≤ 100 000)

The second line contains the number of prisoners in zones 1 – N immediately after the capture, separated by spaces. The number of prisoners in each zone is greater than or equal to 0 and less than or equal to W.

The next Q lines each contain the integers a and b, separated by spaces. (1 ≤ a ≤ N, 0 ≤ b ≤ W) This means that the number of prisoners in zone a has changed to b.

The first line prints the minimum number of special squads needed immediately after the capture.

The next Q lines each print the minimum number of special squads needed after the prisoner count changes.