Problem G
Granite Gradient

You are assisting a geologist in analyzing the history of the Earth’s crust under Gløshaugen. The crust of the Earth has a layered structure, where over time some layers have been eroded from the top due to movement of air and water, while during other periods, dust and sediments accumulate at the top, creating a new layer. For their current study, the geologist is interested in the development of the porosity of the crust over time. Porosity is a measure of how much empty space is present in a material.

The geologist will provide a list of layers, each with a corresponding porosity. They will also provide a set of updates from points in time when the number of layers in the crust changed. Each update will either add or remove a single layer from the top of the crust. For the final report, the geologist needs the sum of the most porous layer’s porosity in the crust after each update.

Input

The first line contains an integer $N$, which is the number of layers in the crust at the starting point. On the next line are $N$ integers $p_{1} \ldots p_{N}$, where $p_{i}$ is the porosity of layer $i$. The next line contains an integer $T$, the number of updates to be performed. The next $T$ lines each contain a historical event affecting the layers, which is either

• “+ $a$”, which means that a new layer with porosity $a$ is added to the top of the crust

• “-”, which means that the top layer is removed from the crust

You are guaranteed that at all times there is at least one layer in the crust.

Output

The sum of the most porous layer’s porosity in the crust after each event.

Limits

• $1 \leq N, T \leq 100000$

• $1 \leq p_{i}, a \leq 1000$

3
1 2 3
2
+ 4
-

7

4
5 10 20 19
5
-
-
+ 15
-
+ 20

75