Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are n applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't).

q events are about to happen (in chronological order). They are of three types:  Application x generates a notification (this new notification is unread).  Thor reads all notifications generated so far by application x (he may re-read some notifications).  Thor reads the first t notifications generated by phone applications (notifications generated in first t events of the first type). It's guaranteed that there were at least t events of the first type before this event. Please note that he doesn't read first t unread notifications, he just reads the very first t notifications generated on his phone and he may re-read some of them in this operation. 

Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.


-----Input-----

The first line of input contains two integers n and q (1 ≤ n, q ≤ 300 000) — the number of applications and the number of events to happen.

The next q lines contain the events. The i-th of these lines starts with an integer type_{i} — type of the i-th event. If type_{i} = 1 or type_{i} = 2 then it is followed by an integer x_{i}. Otherwise it is followed by an integer t_{i} (1 ≤ type_{i} ≤ 3, 1 ≤ x_{i} ≤ n, 1 ≤ t_{i} ≤ q).


-----Output-----

Print the number of unread notifications after each event.


-----Examples-----
Input
3 4
1 3
1 1
1 2
2 3

Output
1
2
3
2

Input
4 6
1 2
1 4
1 2
3 3
1 3
1 3

Output
1
2
3
0
1
2



-----Note-----

In the first sample:  Application 3 generates a notification (there is 1 unread notification).  Application 1 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads the notification generated by application 3, there are 2 unread notifications left. 

In the second sample test:  Application 2 generates a notification (there is 1 unread notification).  Application 4 generates a notification (there are 2 unread notifications).  Application 2 generates a notification (there are 3 unread notifications).  Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.  Application 3 generates a notification (there is 1 unread notification).  Application 3 generates a notification (there are 2 unread notifications).

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation

Complete search


Solutions:
import collections
import sys
(n, q) = map(int, sys.stdin.readline().split(' '))
notifApp = collections.defaultdict(collections.deque)
notifs = collections.deque()
sol = []
total = 0
m = 0
ctd = 0
for i in range(q):
	(tipo, x) = map(int, sys.stdin.readline().split(' '))
	if tipo == 1:
		notifApp[x].append(ctd)
		notifs.append(x)
		total += 1
		ctd += 1
	elif tipo == 2:
		actual = notifApp[x]
		if len(actual) > 0:
			total -= len(actual)
			del notifApp[x]
	else:
		while x > m:
			primero = notifs.popleft()
			actual = notifApp[primero]
			if len(actual) > 0 and actual[0] < x:
				actual.popleft()
				total -= 1
				if len(actual) == 0:
					del notifApp[primero]
			m += 1
	sol.append(total)
sys.stdout.write('\n'.join(map(str, sol)))


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
from collections import *
from bisect import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, q) = gil()
cln = 0
used = [0] * (max(n, q) + 1)
app = [[] for _ in range(n + 1)]
left = 0
notif = deque()
for _ in range(q):
	(tp, op) = gil()
	if tp == 1:
		app[op].append(cln)
		notif.append(cln)
		cln += 1
		left += 1
	elif tp == 2:
		lst = app[op]
		while lst:
			x = lst.pop()
			left -= used[x] ^ 1
			used[x] = 1
	else:
		while notif and notif[0] < op:
			left -= used[notif[0]] ^ 1
			used[notif.popleft()] = 1
	print(left)


from collections import defaultdict, deque
q = deque()
(idx, total) = (0, 0)
vis = defaultdict(deque)
not_valid = set()
max_x = -1
ans = []
(N, Q) = map(int, input().split())
for _ in range(Q):
	(t, x) = map(int, input().split())
	if t == 1:
		q.append((idx, x))
		vis[x].append(idx)
		idx += 1
		total += 1
	elif t == 2:
		while vis[x]:
			i = vis[x].pop()
			not_valid.add(i)
			if i <= max_x - 1:
				continue
			total -= 1
	else:
		while q and (q[0][0] <= x - 1 or q[0][0] in not_valid):
			(j, y) = q.popleft()
			if j not in not_valid:
				total -= 1
				vis[y].popleft()
		max_x = max(max_x, x)
	ans.append(str(total))
print('\n'.join(ans))


import sys
(n, m) = list(map(int, input().split()))
k = 0
pos = 0
L = []
L1 = []
d = {i: [0, -1] for i in range(1, n + 1)}
for i in range(m):
	(a, b) = list(map(int, sys.stdin.readline()[:-1].split()))
	if a == 1:
		d[b][0] += 1
		k += 1
		L.append(b)
	elif a == 2:
		k -= d[b][0]
		d[b][0] = 0
		d[b][1] = len(L)
	else:
		for j in range(pos, b):
			if d[L[j]][0] > 0 and d[L[j]][1] < j + 1:
				k -= 1
				d[L[j]][0] -= 1
		pos = max(pos, b)
	L1.append(k)
sys.stdout.write('\n'.join(map(str, L1)))


import sys, collections
(n, q) = map(int, input().split())
M = collections.defaultdict(collections.deque)
Q = collections.deque()
L = []
s = n = m = 0
for _ in range(q):
	(y, x) = map(int, input().split())
	if 2 > y:
		s += 1
		Q.append(x)
		M[x].append(n)
		n += 1
	elif 3 > y:
		y = M.get(x)
		if y:
			s -= len(y)
			del M[x]
	else:
		while x > m:
			z = Q.popleft()
			y = M.get(z)
			if y and y[0] < x:
				s -= 1
				y.popleft()
				if not y:
					del M[z]
			m += 1
	L.append(s)
sys.stdout.write('\n'.join(map(str, L)))


import collections
(n, q) = list(map(int, input().split()))
Q = collections.deque()
A = n * [0]
B = A[:]
L = []
s = n = 0
for _ in range(q):
	(y, x) = list(map(int, input().split()))
	if 2 > y:
		x -= 1
		Q.append(x)
		B[x] += 1
		A[x] += 1
		s += 1
	elif 3 > y:
		x -= 1
		s -= A[x]
		A[x] = 0
	else:
		while x > n:
			n += 1
			y = Q.popleft()
			B[y] -= 1
			if B[y] < A[y]:
				A[y] -= 1
				s -= 1
	L.append(s)
print('\n'.join(map(str, L)))


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
l = [[] for _ in range(n)]
is_read = []
is_read_idx = 0
ans = 0
prev_t = 0
for _ in range(q):
	(ty, v) = map(int, input().split())
	if ty == 1:
		l[v - 1].append(is_read_idx)
		is_read_idx += 1
		is_read.append(False)
		ans += 1
	elif ty == 2:
		for idx in l[v - 1]:
			if not is_read[idx]:
				is_read[idx] = True
				ans -= 1
		l[v - 1] = []
	elif v > prev_t:
		for idx in range(prev_t, v):
			if not is_read[idx]:
				is_read[idx] = True
				ans -= 1
		prev_t = v
	print(ans)


import collections
(n, q) = map(int, input().split())
Q = collections.deque()
A = [0] * n
B = A[:]
L = []
s = n = 0
for k in range(q):
	(type1, x) = map(int, input().split())
	if type1 == 1:
		x -= 1
		Q.append(x)
		B[x] += 1
		A[x] += 1
		s += 1
	if type1 == 2:
		x -= 1
		s -= A[x]
		A[x] = 0
	if type1 == 3:
		while x > n:
			n += 1
			y = Q.popleft()
			B[y] -= 1
			if B[y] < A[y]:
				A[y] -= 1
				s -= 1
	L.append(str(s))
print('\n'.join(L))


from collections import defaultdict, deque
import sys
g = defaultdict(list)
(n, q) = map(int, input().split())
ans = 0
k = 1
qu = deque()
mark = [0] * (q + 1)
for j in range(q):
	(u, v) = map(int, sys.stdin.readline().split())
	if u == 1:
		qu.append((v, k))
		g[v].append(k)
		k = k + 1
		ans += 1
	elif u == 2:
		for i in g[v]:
			if mark[i] == 0:
				mark[i] = 1
				ans -= 1
		g[v] = []
	else:
		while qu and v >= qu[0][1]:
			m = qu.popleft()
			if mark[m[1]] == 0:
				mark[m[1]] = 1
				ans -= 1
	print(ans)


import sys, collections

def inp():
	return map(int, input().split())
(n, q) = inp()
Q = collections.deque()
A = n * [0]
B = A[:]
L = []
s = n = 0
for _ in range(q):
	(typeq, x) = inp()
	if typeq == 1:
		x -= 1
		Q.append(x)
		B[x] += 1
		A[x] += 1
		s += 1
	elif typeq == 2:
		x -= 1
		s -= A[x]
		A[x] = 0
	else:
		while x > n:
			n += 1
			y = Q.popleft()
			B[y] -= 1
			if B[y] < A[y]:
				A[y] -= 1
				s -= 1
	L.append(s)
sys.stdout.write('\n'.join(map(str, L)))


import sys
import collections
(n, q) = list(map(int, input().split()))
M = {}
Q = collections.deque()
n = 1
s = 0
m = 0
L = []
for i in range(q):
	(c, x) = list(map(int, input().split()))
	if c == 1:
		if x not in M:
			M[x] = collections.deque()
		M[x].append(n)
		Q.append(x)
		n += 1
		s += 1
	elif c == 2:
		if x in M:
			s -= len(M[x])
			M[x] = collections.deque()
	else:
		while x > m:
			z = Q.popleft()
			if z in M and len(M[z]) > 0 and (M[z][0] <= x):
				s -= 1
				M[z].popleft()
			m += 1
	L.append(s)
sys.stdout.write('\n'.join(map(str, L)))


from sys import stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import deque
(n, u) = map(int, input().split())
count = 0
q1 = [deque([]) for i in range(n + 1)]
vis = [0] * (u + 1)
q = deque([])
i = 0
r = 0
for _ in range(u):
	(t, x) = map(int, input().split())
	if t == 1:
		count += 1
		q.append((i, x))
		q1[x].append(i)
		i += 1
	elif t == 2:
		while q1[x]:
			index = q1[x].pop()
			if vis[index] == 0:
				vis[index] = 1
				count -= 1
	else:
		for y in range(r, x):
			(index, app) = q.popleft()
			if vis[index] == 0:
				vis[index] = 1
				count -= 1
				q1[app].popleft()
		if x > r:
			r = x
	print(count)


def main():
	(n, q) = map(int, input().split())
	(vol, tot, l, res) = ([0] * (n + 1), [0] * (n + 1), [], [])
	z = m = 0
	for _ in range(q):
		(t, x) = map(int, input().split())
		if t == 1:
			l.append(x)
			tot[x] += 1
			vol[x] += 1
			z += 1
		elif t == 2:
			z -= vol[x]
			vol[x] = 0
		elif m < x:
			(r, m) = (range(m, x), x)
			for i in r:
				x = l[i]
				tot[x] -= 1
				if vol[x] > tot[x]:
					vol[x] -= 1
					z -= 1
		res.append(z)
	print('\n'.join(map(str, res)))
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, Q) = getInts()
	order = []
	cur_total = 0
	cur_del = -1
	els = [0] * (N + 1)
	del_up_to = [-1] * (N + 1)
	for q in range(Q):
		(T, X) = getInts()
		if T == 1:
			order.append(X)
			els[X] += 1
			cur_total += 1
			print(cur_total)
		elif T == 2:
			cur_total -= els[X]
			els[X] = 0
			del_up_to[X] = max(len(order) - 1, del_up_to[X])
			print(cur_total)
		elif T == 3:
			if X - 1 > cur_del:
				for i in range(cur_del + 1, X):
					if del_up_to[order[i]] < i:
						cur_total -= 1
						del_up_to[order[i]] = i
						els[order[i]] -= 1
				cur_del = X - 1
			print(cur_total)
	return
solve()


(n, q) = map(int, input().split())
l = []
a = [[] for _ in range(n)]
tp = 0
ans = 0
anss = []
for i in range(q):
	(x, b) = map(int, input().split())
	if x == 1:
		l.append(1)
		a[b - 1].append(len(l) - 1)
		ans += 1
	elif x == 2:
		while len(a[b - 1]) > 0:
			z = a[b - 1].pop()
			ans -= l[z]
			l[z] = 0
	else:
		while tp < b:
			ans -= l[tp]
			l[tp] = 0
			tp += 1
	anss.append(str(ans))
print('\n'.join(anss))


import collections
import sys
(n, q) = map(int, input().split())
hash = {}
deque = collections.deque()
messageNumber = 1
unread = 0
L = []
for i in range(q):
	(c, x) = map(int, input().split())
	if c == 1:
		if x not in hash:
			hash[x] = set()
		hash[x].add(messageNumber)
		deque.append((x, messageNumber))
		messageNumber += 1
		unread += 1
	elif c == 2:
		if x in hash:
			xUnread = len(hash[x])
			hash[x] = set()
			unread -= xUnread
	else:
		t = x
		read = 0
		while len(deque) != 0 and deque[0][1] <= t:
			(app, message) = deque.popleft()
			if message in hash[app]:
				read += 1
				hash[app].remove(message)
		unread -= read
	L.append(unread)
print('\n'.join(map(str, L)))


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, q) = ria()
		app_notifications = {}
		app_notifications_read = {}
		notifications = deque()
		read_total = 0
		total_noti = 0
		prevt = 0
		for i in range(q):
			(type, x) = ria()
			if type == 1:
				total_noti += 1
				if x in app_notifications:
					app_notifications[x] += 1
				else:
					app_notifications_read[x] = 0
					app_notifications[x] = 1
				notifications.append([x, app_notifications[x]])
			elif type == 2:
				if x in app_notifications:
					read_total += app_notifications[x] - app_notifications_read[x]
					app_notifications_read[x] = app_notifications[x]
			elif x > prevt:
				k = x - prevt
				while k:
					if app_notifications_read[notifications[0][0]] < notifications[0][1]:
						app_notifications_read[notifications[0][0]] += 1
						read_total += 1
					notifications.popleft()
					k -= 1
				prevt = x
			wi(total_noti - read_total)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
last_2 = [-1] * n
unread_count = [0] * n
total_unread = 0
ev = []
max_3 = 0
ans = []
for i in range(q):
	(t, x) = map(int, input().split())
	x -= 1
	if t == 1:
		ev.append(x)
		unread_count[x] += 1
		total_unread += 1
	elif t == 2:
		total_unread -= unread_count[x]
		unread_count[x] = 0
		last_2[x] = len(ev) - 1
	else:
		for j in range(max_3, x + 1):
			el = ev[j]
			if last_2[el] < j:
				total_unread -= 1
				unread_count[el] -= 1
		max_3 = max(max_3, x + 1)
	ans.append(total_unread)
for a in ans:
	print(a)


from heapq import *
from collections import defaultdict, deque
total = 0
(N, Q) = map(int, input().split())
q = deque()
idx = 0
total = 0
A = [0] * N
B = [0] * N
ans = []
for _ in range(Q):
	(t, x) = map(int, input().split())
	x -= 1
	if t == 1:
		q.append(x)
		A[x] += 1
		B[x] += 1
		total += 1
	elif t == 2:
		total -= A[x]
		A[x] = 0
	else:
		while idx <= x:
			idx += 1
			y = q.popleft()
			B[y] -= 1
			if B[y] < A[y]:
				total -= 1
				A[y] = B[y]
	ans.append(str(total))
print('\n'.join(ans))


from collections import deque as dq
(a, b) = map(int, input().split())
arr = dq()
p = [0] * a
q = list(p)
tot = 0
no = 0
l = dq()
for i in range(0, b):
	(x, y) = map(int, input().split())
	if x == 1:
		arr.append(y - 1)
		p[y - 1] = p[y - 1] + 1
		q[y - 1] = q[y - 1] + 1
		tot = tot + 1
		l.append(tot)
	elif x == 2:
		tot = tot - p[y - 1]
		p[y - 1] = 0
		l.append(tot)
	else:
		while y > no:
			w = arr[0]
			arr.popleft()
			q[w] = q[w] - 1
			if p[w] > q[w]:
				p[w] = p[w] - 1
				tot = tot - 1
			no = no + 1
		l.append(tot)
for i in l:
	print(i)


(n, q) = map(int, input().split())
xi = [[0] * (n + 1) for i in range(2)]
noti = []
ans = ''
num = 0
num2 = 0
num3 = 0
while q > 0:
	(typ, xt) = map(int, input().split())
	if typ == 1:
		xi[0][xt] += 1
		noti += [xt]
		num += 1
		num2 += 1
	elif typ == 3:
		for i in range(num3, xt):
			if i + 1 > xi[1][noti[i]]:
				xi[0][noti[i]] -= 1
				num -= 1
		num3 = max(num3, xt)
	else:
		num -= xi[0][xt]
		xi[0][xt] = 0
		xi[1][xt] = num2
	ans += str(num)
	ans += '\n'
	q -= 1
print(ans)


from sys import stdin
input = stdin.readline
(n, q) = list(map(int, input().split()))
arr = [tuple(map(int, input().split())) for _ in range(q)]
adj = [[] for _ in range(n + 1)]
(curr, cnt, res, vis) = (0, 0, [], [])
for (t, v) in arr:
	if t == 1:
		adj[v].append(len(vis))
		vis.append(0)
		cnt += 1
	elif t == 2:
		for u in adj[v]:
			if not vis[u]:
				vis[u] = 1
				cnt -= 1
		adj[v] = []
	else:
		while v > curr:
			if not vis[curr]:
				vis[curr] = 1
				cnt -= 1
			curr += 1
	res.append(cnt)
print('\n'.join(map(str, res)))


from sys import stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
print = stdout.write
(n, q) = map(int, input().split())
d = [[] for i in range(n + 1)]
mark = []
ans = 0
inde = 0
t = 0
for i in range(q):
	(event, x) = map(int, input().split())
	if event == 1:
		ans += 1
		d[x].append(inde)
		inde += 1
		mark.append(False)
	elif event == 2:
		for j in d[x]:
			if not mark[j]:
				mark[j] = True
				ans -= 1
		d[x] = []
	else:
		for j in range(t, x):
			if not mark[j]:
				mark[j] = True
				ans -= 1
		if x > t:
			t = x
	print(str(ans) + '\n')


import collections
(n, q) = map(int, input().split())
dq = collections.deque()
l = n * [0]
p = list(l)
ans = 0
t = 0
ansl = []
while q:
	(a, b) = map(int, input().split())
	if a == 1:
		dq.append(b - 1)
		(l[b - 1], p[b - 1]) = (l[b - 1] + 1, p[b - 1] + 1)
		ans = ans + 1
	elif a == 2:
		ans = ans - l[b - 1]
		l[b - 1] = 0
	else:
		while b > t:
			t = t + 1
			j = dq.popleft()
			p[j] = p[j] - 1
			if l[j] > p[j]:
				l[j] = l[j] - 1
				ans = ans - 1
	ansl.append(str(ans))
	q = q - 1
print('\n'.join(ansl))


(n, q) = map(int, input().split())
stacks = [[] for i in range(n + 1)]
queue = []
q_start = 0
unread = 0
ans = []
for i in range(q):
	(action, num) = map(int, input().split())
	if action == 1:
		queue.append(0)
		stacks[num].append(len(queue) - 1)
		unread += 1
	elif action == 2:
		for i in range(len(stacks[num])):
			if stacks[num][i] >= q_start and queue[stacks[num][i]] == 0:
				queue[stacks[num][i]] = 1
				unread -= 1
		stacks[num] = []
	else:
		for i in range(q_start, num):
			if queue[i] == 0:
				queue[i] = 1
				unread -= 1
		q_start = max(q_start, num)
	ans.append(unread)
print('\n'.join(map(str, ans)))


(n, q) = list(map(int, input().split()))
count = [0 for i in range(n + 1)]
queue = []
read = set()
unread = 0
ans = []
last_q_idx = 0
last_app_idx = [1 for i in range(n + 1)]
for i in range(q):
	(action, num) = list(map(int, input().split()))
	if action == 1:
		queue.append((num, count[num] + 1))
		count[num] += 1
		unread += 1
	elif action == 2:
		for number in range(last_app_idx[num], count[num] + 1):
			if (num, number) not in read:
				read.add((num, number))
				unread -= 1
		last_app_idx[num] = max(last_app_idx[num], count[num])
	else:
		for idx in range(last_q_idx, num):
			(app, number) = queue[idx]
			if (app, number) not in read:
				read.add((app, number))
				last_app_idx[app] = max(last_app_idx[app], number)
				unread -= 1
		last_q_idx = max(last_q_idx, num)
	ans.append(unread)
print('\n'.join(map(str, ans)))


from sys import stdin
input = stdin.readline
(n, q) = map(int, input().split())
is_read_index = 0
is_read = []
l = [[] for i in range(n)]
ans = 0
prev = 0
for _ in range(q):
	(t, v) = map(int, input().split())
	if t == 1:
		l[v - 1].append(is_read_index)
		is_read_index += 1
		is_read.append(False)
		ans += 1
	elif t == 2:
		for idx in l[v - 1]:
			if not is_read[idx]:
				is_read[idx] = True
				ans -= 1
		l[v - 1] = []
	elif v > prev:
		for idx in range(prev, v):
			if not is_read[idx]:
				is_read[idx] = True
				ans -= 1
		prev = v
	print(ans)