Faucets

Time limit2sMemory limit1024 MB

Summary

Each operation changes one faucet's flow or open state, and the task asks for the total open flow after the start and after every operation.

Level: Easy2 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Problem

A water tank is connected to $N$ faucets. Each faucet has a screw and a toggle button. Turning the screw adjusts how much water flows out, and pressing the toggle button opens or closes the faucet. The amount of water that enters the tank in one minute is the sum of the water flowing out of the open faucets.

Specifically, you can perform the following operations on a faucet.

Turn the screw so that the faucet, while open, releases $x$ liters of water per minute.
Press the toggle button. If the faucet is open, it closes. If it is closed, it opens.

At the start, every faucet is open, and the $i$ -th faucet releases $A_i$ liters of water per minute. You will perform $Q$ operations on these faucets. Compute the amount of water that enters the tank in one minute at the start and after each operation.

Input

The first line contains the number of faucets $N$ . $(1\leq N\leq 200\,000)$

The second line contains $A_1, A_2, \cdots, A_N$ , the amounts of water released by the faucets at the start, separated by spaces. $(1\le A_i\le 10^9)$

The third line contains the number of operations $Q$ . $(1\leq Q\leq 200\,000)$

From the fourth line, each of the next $Q$ lines contains one operation in one of the following forms.

1 i x means the screw of the $i$ -th faucet was turned so that it releases $x$ liters of water per minute. $(1\le i\le N$ , $1\le x\le 10^9)$
2 i means the toggle button of the $i$ -th faucet was pressed. $(1\leq i\leq N)$

All numbers in the input are integers.

Output

Print $Q+1$ lines. The first line is the amount of water that enters the tank in one minute when no operation has been performed, in liters. The $i$ -th of the next $Q$ lines is the amount of water that enters the tank in one minute after the first $i$ operations have been performed, in liters.

Hint

Because the input and output are large, using fast I/O is recommended.

Examples2

Example 1
Input
```
3
6 1 4
4
2 1
2 3
1 2 3
2 3
```
Expected output
```
11
5
1
3
7
```

Example 2

Input

5
1000000000 1000000000 1000000000 1000000000 1000000000
4
1 1 999999999
2 1
1 1 999999998
2 1

Expected output