flash-of-two-worlds

Barry Allen and Jay Garrick are arch-rivals. To prove himself superior than Barry, Jay takes Barry to a Lighthouse, consisting of 'N' bulbs. Jay gives Barry a sequence of n integers. The circuit of bulbs is made in following way:

•   If the bulb on ith position is turned on/off then the ith bulb automatically turns on/off respectively. 

•   Bulb 0 is MCB, if it is turned on/off then all bulbs will turn on/off.

Now Jay uses his speed force to turn on/off (operations) the bulbs quickly and asks Barry to tell how many bulbs are on and off at some particular instances.

The operations are given in as "Operation P" are defined in following way:

Operation 1: Turn ON Pth bulb.

Operation 2: Turn OFF Pth bulb.

Operation 3: Asks Barry to tell 'S' depending on the current state of Pth bulb.

•   If Pth bulb is ON then S is the number of bulbs which would turn OFF when Pth bulb is turned OFF.

•   If Pth bulb is OFF then S is the number of bulbs whose state will not be effected on turning Pth Bulb ON.

Now Barry requires your help to answer Jay. 

Note: Initially all the bulbs are ON

Input:

The first line of input contains an integer N denoting the number of bulbs in the light house.

The next line contains N space separated positive integers, as given in the problem statement.

The third line contains Q, the number of operations performed by Jay.

Each of the next Q lines contain two integers, the type of operation and P.

Output:

For each Operation 3, output S as defined in problem statement.

Constraints:

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

1 ≤ Operation ≤ 3

1 ≤ P ≤ N

SAMPLE INPUT
3
2 0 1
5
3 1
1 1
3 1
2 1
3 1

SAMPLE OUTPUT
1
1
0

Explanation

Initially all the bulbs are ON, and there is only 1 bulb which will turn OFF if Bulb 1 is turned OFF (Bulb 3). Now Bulb 1 is turned ON which will do no effect. Again the answer will be same as for previous case. Then Bulb 1 is turned OFF, turning OFF bulb 3. Thus the answer is 0.

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: