Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.

Date de ieșire

Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv 0 în caz contrar.

Restricții și precizări

• 1 ≤ n ≤ 25000
• 1 ≤ m ≤ 200000
• elementele celor 2 vectori vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

7
1 2 5 6 9 10 14 
8
8 14 9 14 16 15 4 2 

Ieșire

0 1 1 1 0 0 0 1

using namespace std;

bool cautare(int li, int ls, int v[], int y)
{
if(li > ls)
return false;
int mi = (li + ls) / 2;

if(v[mi] == y)
    return true;

if(v[mi] > y)
    return cautare(li, mi - 1, v, y);

return cautare(mi + 1, ls, v, y);

}

int main()
{
int v[25001], n, m, x;

cin>>n;
for(int i=1;i<=n;i++)
    cin>>v[i];
cin>>m;

for(int i=1;i<=m;i++)
{
    cin>>x;
    if(cautare(1, n, v, x))
        cout<<1<<' ';
    else
        cout<<0<<' ';
}

}