B. Applejack and Storages

B. Applejack and Storages

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 nn 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:

• ++ xx: the storehouse received a plank with length xx
• −− xx: one plank with length xx was removed from the storehouse (it is guaranteed that the storehouse had some planks with length xx).

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 nn (1≤n≤1051≤n≤105): the initial amount of planks at the company's storehouse, the second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1051≤ai≤105): the lengths of the planks.

The third line contains a single integer qq (1≤q≤1051≤q≤105): the number of events in the company. Each of the next qq 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 xx (1≤x≤1051≤x≤105).

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

Copy

6
1 1 1 2 1 1
6
+ 2
+ 1
- 1
+ 2
- 1
+ 2

output

Copy

NO
YES
NO
NO
NO
YES

Note

After the second event Applejack can build a rectangular storage using planks with lengths 11, 22, 11, 22 and a square storage using planks with lengths 11, 11, 11, 11.

After the sixth event Applejack can build a rectangular storage using planks with lengths 22, 22, 22, 22 and a square storage using planks with lengths 11, 11, 11, 11.

=========================================================================

开始做之前让我感到棘手的是2 4的次数会产生重复，后来发现根本没必要，直接统计2,4的次数即可，一个4会带来两个2，到时候直接扣除即可

即两个4可以，一个4，外加4个2也可以，之所以是4个就可以，是因为要扣除1一个4的影响。

不少题解动辄几百行数据结构来解这个题，感到不解的同时，也只能感叹一下本是用来方便问题解决的算法成了掣肘思维的绊脚石

# include<iostream>
# include<string.h>
# include<vector>

using namespace std;

int cnt[100000+10];
int two=0,four=0;
int main ()
{


    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;

        cnt[x]++;
        if(cnt[x]%2==0)
            two++;
        if(cnt[x]%4==0)
            four++;
    }

    int t;
    cin>>t;

    while(t--)
    {
        char ch;
        int x;

        cin>>ch>>x;

        if(ch=='-')
        {
            cnt[x]--;

            if(cnt[x]%2==1)
                two--;

            if(cnt[x]%4==3)
                four--;

        }
        else
        {
            cnt[x]++;

            if(cnt[x]%2==0)
                two++;
            if(cnt[x]%4==0)
                four++;
        }

        if(four>=2||(four>=1&&two>=4))
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }


    return  0;

}