SMMR-085: Relax

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int N = 1e6 + 10;
using pi = pair <int, int>;
pi ar[N];
int n;

int Query(int x){
    int l = 1, r = n, mn = INF;
    while(l <= r){
        int mid = (l + r) / 2;
        if(ar[mid].first == x)
            mn = min(mn, mid), r = mid - 1;
        if(ar[mid].first < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return mn;
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        ar[i] = {x, i};
    }

    sort(ar + 1, ar + n + 1);

    int m;
    scanf("%d", &m);

    for(int i=1;i<=m;i++){
        int x;
        scanf("%d", &x);
        int Q = Query(x);
        if(Q == INF) printf("Not found\n");
        else printf("%d\n", ar[Q].second);
    }

    return 0;
}