Magic Orbs

Time limit1sMemory limit1024 MB

Summary

Orbs dropped on zone 1 roll right past strictly lower zones and raise the zone where they stop; report zone 1's value after each batch.

Problem

$N$ zones are arranged in a straight line. The zones are numbered $1, 2, \cdots, N$ from left to right, and the initial value of zone $i$ is $V_i$ .

A magic orb raises the values of zones. When an orb is dropped on zone 1, it behaves as follows.

Let $p$ be the zone where the orb currently sits. If $p < N$ and the value of zone $p+1$ is lower than the value of zone $p$ , the orb moves to zone $p+1$ . Repeat this until the orb stops moving.
If the orb does not move from zone $p$ , add $1$ to the value of that zone.

A wizard left you $Q$ tasks of two kinds, to be processed in order. All results accumulate. At least one task asks for the value of zone 1.

1 x: Drop $x$ orbs onto zone 1, one at a time. Each orb finishes its movement and increases the value of the zone where it stops. Only then is the next orb dropped.
2: Print the value of zone 1.

The first line contains $N$ and $Q$ , separated by a space.

The second line contains the initial values $V_1, V_2, \cdots, V_N$ , separated by spaces.

Each of the next $Q$ lines contains one task.

For each task of type 2, print the value of zone 1 on its own line.