Contest 5_E

#include<bits/stdc++.h>

using namespace std;

long long i, n;
long long j, q;
long long a[100000];

void b_search(long long key)
{
    long long l=0;
    long long h=n-1;
    long long m;
    long long ans_l, ans_h;

    while(l<=h){
        m=(l+h)/2;

        if(a[m]==key){
            ans_l=a[m-1];
            ans_h=a[m+1];
            printf("%lld %lld\n", ans_l,ans_h);
            break;
        }

        else if(a[m]<key){
            if(a[m+1]>key){
                ans_l=a[m];
                ans_h=a[m+1];
                printf("%lld %lld\n", ans_l,ans_h);
                break;
            }
            else{
                l=m+1;
            }
        }
        else if(a[m]>key){
            if(a[m-1]<key){
                ans_l=a[m-1];
                ans_h=a[m];
                printf("%lld %lld\n", ans_l,ans_h);
                break;
            }
            else{
                h=m-1;
            }
        }
    }
}

int main()
{
    long long key;

    scanf("%lld", &n);
    for(i=0;i<n;i++)
        scanf("%lld", &a[i]);

    scanf("%lld", &q);
    for(j=0;j<q;j++){
        scanf("%lld", &key);

        if(key>=a[n-1]){
            printf("%lld %c\n", a[n-1],'X');
        }
        else if(key<=a[0]){
            printf("%c %lld\n", 'X',a[0]);
        }
        else{
            b_search(key);
        }
    }
    return 0;
}