Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Funmondi Contest!

By Shahwat_Has9 · Limits 1s, 50 MB

There is a contest being held on Funmondi named ‘Funmondy Inter School Programming Contest’. You are one of the head organizers of this contest. So you have to keep track of so many things. One of them is how many different school student is currently present in the venue.

Each school has an id number. There are n schools participating in this contest. You know how many students from each school are currently present at the venue. But the contestant can leave or enter the venue at any moment as the gate is open. But you will get to know a student from which school is checking in or checking out in the venue.

This is a huge problem to keep track of, right? So you decided to build a program that will handle all the information for you and keep the record of how many different schools are currently present at this moment.

Input

In the first line, You will receive n and q, which indicates how many schools are going to participate in this contest and query respectively. The next line will contain n different numbers (a1, a2, a3 ….. an). ai represents the number of students from the ith school. In the next q lines, you will receive two types of queries.

1 v: One student from vth school left the venue.

2 v: One student from vth school entered the venue.

Constraints:
1 <= v <= n <= 200000
1 <= q <= 200000
0 <= ai <= 100000

It is guaranteed that all operations are valid.

Output

After each query, you will print how many different schools are currently present in the venue.

Sample

InputOutput
8 4
5 6 7 8 0 0 1 4
2 5
2 6
1 7
1 1
7
8
7
7

After the first query the present schools are: 1, 2, 3, 4, 5, 7, 8.

After the second query the present schools are: 1, 2, 3, 4, 5, 6, 7, 8.

After the third query the present schools are: 1, 2, 3, 4, 5, 6, 8.

After the fourth query the present schools are: 1, 2, 3, 4, 5, 6, 8.


Use faster I/O


Discussion
Statistics

86% Solution Ratio

Pitu75Earliest, 1M ago

jaberndcFastest, 0.0s

PrimeXLightest, 2.2 MB

mashfiqur404Shortest, 330B

Submit

Login to submit