Uva 10611 - The Playboy Chimp

/*

    Verdict : Accepted
    Time: 0.000

*/

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define N 1000100
using namespace std;

typedef long long LL;

LL ar[N];

LL lowerBound(LL itm, LL sz)
{
    LL lo=1, hi=sz, mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(ar[mid] == itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

LL upperBound(LL itm, LL sz)
{
    LL lo=1, hi=sz, mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(ar[mid] == itm)
        {
            lo = mid+1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int main()
{
    int n , i;
    sf("%d",&n);

    for(i=1;i<=n;i++)
    {
        sf("%lld",&ar[i]);
    }

    int query;
    sf("%d",&query);

    while(query--)
    {
        LL x;
        sf("%lld",&x);

        LL lw = lowerBound(x, n);
        LL up = upperBound(x, n);

        if(!ar[lw-1])
        {
            pf("X");
        }

        else
        {
            pf("%lld",ar[lw-1]);
        }

        if(!ar[up])
        {
            pf(" X\n");
        }

        else
        {
            pf(" %lld\n",ar[up]);
        }
    }

    return 0;
}