This year in Equestria was a year of plenty, so Applejack has decided to build some new apple storages. According to the advice of the farm designers, she chose to build two storages with non-zero area: one in the shape of a square and another one in the shape of a rectangle (which possibly can be a square as well).

Applejack will build the storages using planks, she is going to spend exactly one plank on each side of the storage. She can get planks from her friend's company. Initially, the company storehouse has $n$ planks, Applejack knows their lengths. The company keeps working so it receives orders and orders the planks itself. Applejack's friend can provide her with information about each operation. For convenience, he will give her information according to the following format:

  $+$ $x$: the storehouse received a plank with length $x$  $-$ $x$: one plank with length $x$ was removed from the storehouse (it is guaranteed that the storehouse had some planks with length $x$). 

Applejack is still unsure about when she is going to order the planks so she wants to know if she can order the planks to build rectangular and square storages out of them after every event at the storehouse. Applejack is busy collecting apples and she has completely no time to do the calculations so she asked you for help!

We remind you that all four sides of a square are equal, and a rectangle has two pairs of equal sides.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$): the initial amount of planks at the company's storehouse, the second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$): the lengths of the planks.

The third line contains a single integer $q$ ($1 \le q \le 10^5$): the number of events in the company. Each of the next $q$ lines contains a description of the events in a given format: the type of the event (a symbol $+$ or $-$) is given first, then goes the integer $x$ ($1 \le x \le 10^5$).


-----Output-----

After every event in the company, print "YES" if two storages of the required shape can be built from the planks of that company's set, and print "NO" otherwise. You can print each letter in any case (upper or lower).


-----Example-----
Input
6
1 1 1 2 1 1
6
+ 2
+ 1
- 1
+ 2
- 1
+ 2

Output
NO
YES
NO
NO
NO
YES



-----Note-----

After the second event Applejack can build a rectangular storage using planks with lengths $1$, $2$, $1$, $2$ and a square storage using planks with lengths $1$, $1$, $1$, $1$.

After the sixth event Applejack can build a rectangular storage using planks with lengths $2$, $2$, $2$, $2$ and a square storage using planks with lengths $1$, $1$, $1$, $1$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
planks=[0]*100000
pairs=0
squares=0
for x in a:
    planks[x-1]+=1
    if planks[x-1]%2==0:
        pairs+=1
        if planks[x-1]%4==0:
            squares+=1
for f in range(int(input())):
    inp=list(input().split())
    p=inp[0]
    i=int(inp[1])
    i-=1
    if p=="+":
        planks[i]+=1
        if planks[i]%2==0:
            pairs+=1
            if planks[i]%4==0:
                squares+=1
    else:
        if planks[i]%2==0:
            pairs-=1
            if planks[i]%4==0:
                squares-=1
        planks[i]-=1
    if squares>0 and pairs>3:
        print("YES")
    else:
        print("NO")

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [0] * (10 ** 5 + 5)
cnt4 = 0
cnt2 = 0
for i in range(n):
    b[a[i]] += 1
for elem in b:
    cnt4 += elem // 4
    cnt2 += elem // 2
for i in range(q):
    s = input().split()
    x = int(s[1])
    cnt4 -= b[x] // 4
    cnt2 -= b[x] // 2    
    if s[0] == "+":
        b[x] += 1
    else:
        b[x] -= 1
    cnt4 += b[x] // 4
    cnt2 += b[x] // 2
    if cnt4 > 0:
        cnt = cnt2 - 2
        if cnt >= 2:
            print("YES")
        else:
            print("NO")
    else:
        print("NO")

import sys

input=sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))
data=[0]*(10**5+1)
for i in range(n):
    data[a[i]]+=1

zero,two,four,six,eight=0,0,0,0,0
for i in range(1,10**5+1):
    if data[i]<=1:
        zero+=1
    elif data[i]<=3:
        two+=1
    elif data[i]<=5:
        four+=1
    elif data[i]<=7:
        six+=1
    else:
        eight+=1

for i in range(int(input())):
    t,m=input().split()
    m=int(m)
    if t=="+":
        if data[m]==7:
            eight+=1
            six-=1
        elif data[m]==5:
            six+=1
            four-=1
        elif data[m]==3:
            four+=1
            two-=1
        elif data[m]==1:
            two+=1
        data[m]+=1
    else:
        if data[m]==8:
            eight-=1
            six+=1
        elif data[m]==6:
            six-=1
            four+=1
        elif data[m]==4:
            four-=1
            two+=1
        elif data[m]==2:
            two-=1
        data[m]-=1
    if eight:
        print("YES")
    elif six>=2:
        print("YES")
    elif six==1:
        if four or two:
            print("YES")
        else:
            print("NO")
    elif four>=2:
        print("YES")
    elif four and two>=2:
        print("YES")
    else:
        print("NO")

n = int(input())
a = list(map(int, input().split()))
q = int(input())
cnt8 = 0
cnt6 = 0
cnt4 = 0
cnt2 = 0
d = dict()
for i in a:
    d[i] = d.get(i, 0) + 1
for i in d.values():
    if i >= 8:
        cnt8 += 1
    if i >= 6:
        cnt6 += 1
    if i >= 4:
        cnt4 += 1
    if i >= 2:
        cnt2 += 1
for i in range(q):
    t, val = input().split()
    val = int(val)

    d[val] = d.get(val, 0)

    if d[val] >= 8:
        cnt8 -= 1
    if d[val] >= 6:
        cnt6 -= 1
    if d[val] >= 4:
        cnt4 -= 1
    if d[val] >= 2:
        cnt2 -= 1

    if t == '+':
        d[val] += 1
    else:
        d[val] -= 1

    if d[val] >= 8:
        cnt8 += 1
    if d[val] >= 6:
        cnt6 += 1
    if d[val] >= 4:
        cnt4 += 1
    if d[val] >= 2:
        cnt2 += 1

    if cnt8 >= 1:
        print("YES")
    elif cnt6 > 1 or (cnt6 == 1 and cnt2 >= 2):
        print("YES")
    elif cnt4 > 1 or (cnt4 == 1 and cnt2 >= 3):
        print("YES")
    else:
        print("NO")


from sys import stdin

n = int(stdin.readline())

a = list(map(int,stdin.readline().split()))

q = int(stdin.readline())

lis = [0] * (10**5+10)

four = 0
two  = 0

for i in a:
    lis[i] += 1
    if lis[i] % 2 == 0:
        two += 1
    if lis[i] % 4 == 0:
        four += 1


for loop in range(q):

    c,l = stdin.readline().split()
    l = int(l)

    if c == "+":
        lis[l] += 1
        if lis[l] % 2 == 0:
            two += 1
        if lis[l] % 4 == 0:
            four += 1

    else:
        if lis[l] % 2 == 0:
            two -= 1
        if lis[l] % 4 == 0:
            four -= 1
        lis[l] -= 1

    if four >= 1 and two >= 4:
        print ("YES")
    else:
        print ("NO")


import sys
input=sys.stdin.readline
n=int(input())
L=list(map(int,input().split()))
q=int(input())
ct2=0
ct4=0
ct6=0
ct8=0
ct=[0]*(10**5+10)
for i in L:ct[i]+=1
for i in ct:
    if i>1:ct2+=1
    if i>3:ct4+=1
    if i>5:ct6+=1
    if i>7:ct8+=1
for i in ' '*q:
    a,b=input().split()
    b=int(b)
    if a=='+':
        ct[b]+=1
        if ct[b]==2:ct2+=1
        if ct[b]==4:ct4+=1
        if ct[b]==6:ct6+=1
        if ct[b]==8:ct8+=1
    else:
        ct[b]-=1
        if ct[b]==1:ct2-=1
        if ct[b]==3:ct4-=1
        if ct[b]==5:ct6-=1
        if ct[b]==7:ct8-=1
    if ct2>=2 and ct6>=1:print('YES')
    elif ct2>=3 and ct4>=1:print('YES')
    elif ct4>=2:print('YES')
    elif ct8:print('YES')
    else:print('NO')

from collections import defaultdict

spc = {2: 0, 4: 0, 6: 0, 8: 0}
def handle(is_plus, x):
    if is_plus:
        counts[x] += 1
        for v in [2, 4, 6, 8]:
            if counts[x] == v:
                spc[v] += 1
    else:
        counts[x] -= 1
        for v in [2, 4, 6, 8]:
            if counts[x] == v-1:
                spc[v] -= 1

n = int(input())

counts = defaultdict(int)
a = list(map(int, input().split()))
for x in a:
    handle(True, x)

q = int(input())


for _ in range(q):
    c, x = input().split()
    x = int(x)
    
    handle(c=="+", x)
    if spc[8] >= 1:
        print("YES")
    elif spc[6] >= 1 and spc[2] >= 2:
        print("YES")
    elif spc[4] >= 2:
        print("YES")
    elif spc[4] >= 1 and spc[2] >= 3:
        print("YES")
    else:
        print("NO")


mod=998244353
n=int(input())
a=list(map(int,input().split()))
d=dict()
two=0
four=0
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
for i in d:
    two+=d[i]//2
    four+=d[i]//4
m=int(input())
for i in range (m):
    s=input().split()
    if s[0]=='+':
        l=int(s[1])
        if l in d:
            d[l]+=1
        else:
            d[l]=1
        if d[l]%2==0:
            two+=1
        if d[l]%4==0:
            four+=1
    else:
        l=int(s[1])
        d[l]-=1
        if d[l]%2==1:
            two-=1
        if d[l]%4==3:
            four-=1
    if four>0 and two>3:
        print("YES")
    else:
        print("NO")

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
c = Counter(a)
d = {2:{},4:{}}
for i in c:
	if c[i]>=4:
		d[4][i] = 0
	elif c[i]>=2:
		d[2][i] = 0


for i in range(q):
	a,b = input().split()
	b = int(b)
	if a=="+":
		if b in c:
			c[b] += 1
		else:
			c[b] = 1
		if c[b] == 4:
			d[4][b] = 0
			del d[2][b]
		elif c[b]==2:
			d[2][b] = 0
	else:
		c[b] -= 1
		if c[b]==3:
			del d[4][b]
			d[2][b] = 0
		elif c[b]==1:
			del d[2][b]

	# print (c)
	# print (d)
	if len(d[4])>=2:
		print ("YES")
	elif len(d[4])==1 and len(d[2])>=2:
		print ("YES")
	elif len(d[4])==1:
		for k in d[4]:
			ind = k
			break
		if len(d[2])==1 and c[ind]>=6:
			print ("YES")
		elif len(d[2])==0 and c[ind]>=8:
			print ("YES")
		else:
			print ("NO")
	else:
		print ("NO")



import sys
import math
def II():
	return int(sys.stdin.readline())

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

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

def SI():
	return sys.stdin.readline().strip()
n = II()
a = LI()
d = [0]*(10**5+1)
t = 0
e = 0
for i in a:
	d[i]+=1
	if d[i]%4 == 0:
		t+=1
		e-=1
	elif d[i]%2 == 0:
		e+=1
for j in range(int(input())):
	q,i = input().split()
	i = int(i)
	if q == "+":
		d[i]+=1
		if d[i]%4 == 0:
			t+=1
			e-=1
		elif d[i]%2 == 0:
			e+=1
	else:
		d[i]-=1
		if d[i]%4 == 3:
			t-=1
			e+=1
		elif d[i]%4 == 1:
			e-=1
	boo = False
	if t > 1:
		boo = True
	elif t == 1 and e>1:
		boo = True
	print("YES" if boo else "NO")


import sys

I = [0 for i in range(10**5+1)]
y2, y4, y6, y8 = 0, 0, 0, 0
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
for i in range (0, n):
    I[a[i]] = I[a[i]] + 1
    if I[a[i]] == 2:
        y2 = y2 + 1
    if I[a[i]] == 4:
        y4 = y4 + 1
    if I[a[i]] == 6:
        y6 = y6 + 1
    if I[a[i]] == 8:
        y8 = y8 + 1
Q = int(sys.stdin.readline().strip())
for q in range(Q):
    s, x = sys.stdin.readline().strip().split()
    x = int(x)
    if s == "+":
        I[x] = I[x] + 1
        if I[x] == 2:
            y2 = y2 + 1
        if I[x] == 4:
            y4 = y4 + 1
        if I[x] == 6:
            y6 = y6 + 1
        if I[x] == 8:
            y8 = y8 + 1
    if s == "-":
        I[x] = I[x] - 1
        if I[x] == 1:
            y2 = y2 - 1
        if I[x] == 3:
            y4 = y4 - 1
        if I[x] == 5:
            y6 = y6 - 1
        if I[x] == 7:
            y8 = y8 - 1
    if y4 >= 1 and y2 + y4 + y6 + y8 >= 4:
        print("YES")
    else:
        print("NO")