bdfz_2024_summer/day10/U178578/U178578.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct Node{
    int k,x,q;
    // bool isdone;
};

const int MAX_N=5e5+5;
int n,q;
int a[MAX_N],/*x[MAX_N],k[MAX_N],*/ans[MAX_N],xdir[MAX_N];
Node nodes[MAX_N];
int pn=0,p1=1;
int readint();

signed main(signed argc,char *argv[]){
    n=readint();
    for(int i=1;i<=n;i++){
        a[i]=readint();
        xdir[a[i]]=i;
    }
    q=readint();

    for(int i=1;i<=q;i++){
        int k = readint(),x=readint();
        // k[i]=readint();
        // x[i]=readint();
        nodes[++pn]={k,x,i};
    }
    sort(nodes+1,nodes+pn+1,[](Node a,Node b)->bool{
        return a.k<b.k;
    });
    pn++;
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=n-1-i;j++){
            if(a[j]>a[j+1]){
                xdir[a[j]]=j+1;
                xdir[a[j+1]]=j;
                swap(a[j],a[j+1]);
            }
        }
        if(p1==pn){
            break;
        }
        while(p1!=pn&&nodes[p1].k==i){
            auto &now = nodes[p1++];
            ans[now.q]=xdir[now.x];
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<endl;
    }
}

int readint(){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*w;
}