• 决策单调性分治

容易发现将询问离线排序之后，值更大的询问能取到的最优决策点是递增的。 这是因为考虑a数组，如果出现一个逆序对，那么右边那个位置一定是不优的； 因此决策点一定是一个下标递增，值也递增的数列。

决策单调性考虑分治，对于一个询问的值 ，只需枚举当前决策区间内的每个点 ，答案是 中比 大的和 中比 大的数个数的和。 使用主席树查询区间中比某个数大的个数即可。

复杂度两个 。

///*****Sellaris*****///


#include <bits/stdc++.h>
//#include <bits/extc++.h>
#include<ext/rope>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//用tree
#include<ext/pb_ds/hash_policy.hpp>//用hash
#include<ext/pb_ds/trie_policy.hpp>//用trie
#include<ext/pb_ds/priority_queue.hpp>//用priority_queue

#define ll long long
#define x first
#define y second

typedef unsigned long long ull;
typedef std::pair<int,int> pii;

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

const int maxn=2e5+10;
const int mo=1e9+7;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}

int n,m;
int a[maxn];
pii q[maxn];
int ans[maxn];

struct tree{
    int l,r,sum;
}tr[maxn*40];
int tot,root[maxn];

inline int build(int &p,int l,int r){
    p=++tot;
    if(l==r) return 1;
    int mid=(l+r)>>1;
    build(tr[p].l,l,mid);
    build(tr[p].r,mid+1,r);
    return 1;
}
inline void modify(int &p,int q,int l,int r,int k){
    p=++tot;
    tr[p]=tr[q];
    tr[p].sum++;//push_up
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(k<=mid) modify(tr[p].l,tr[q].l,l,mid,k);
    else modify(tr[p].r,tr[q].r,mid+1,r,k);
}
inline int query(int p,int q,int l,int r,const int k){
    if (l==r) return tr[q].sum-tr[p].sum;
    int mid=(l+r)>>1;
    if (mid>=k)
        return tr[tr[q].r].sum-tr[tr[p].r].sum + query(tr[p].l,tr[q].l,l,mid,k);
    else 
        return query(tr[p].r,tr[q].r,mid+1,r,k);
}

pii clac(int x,int l,int r){
	int v=q[x].x;
	int ans=1e9,pos;
	for(int i=l;i<=r;i++){
		int val=query(root[0],root[i-1],1,n+m,v+1) + query(root[i],root[n],1,n+m,max(v,a[i])+1);
		if(val<=ans) pos=i;
		ans=min(ans , val);
		//cout<<"I====="<<i<<"\n";
		//cout<<"q="<<v<<" val="<<val<<"\n";
		//cout<<"q[0,i-1]"<<" "<<query(root[0],root[i-1],1,n+m,v)<<"\n";
		//cout<<"q[i+1,n]"<<" "<<query(root[i],root[n],1,n+m,a[i])<<"\n";
	}
	
	return {ans,pos};
	//query(root[0],root[i-1],1,n+m,v)
	//query(root[i],root[n],1,n+m,a[i])
}
void dac(int l,int r,int ansl,int ansr){
	int mid=(l+r)>>1;
	auto [v,pos]=clac(mid,ansl,ansr);
	ans[q[mid].y]=v;
	//l~mid-1 mid+1~r
	//cout<<"query="<<q[mid].x<<" l="<<ansl<<" r="<<ansr<<" \n";
	//cout<<"ans="<<v<<"\n";
	if(l<=mid-1)dac(l,mid-1,ansl,pos);
	if(r>=mid+1)dac(mid+1,r,pos,ansr);
}
vector<int>lsh;
inline void solve(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(), lsh.push_back(a[i]);
	m=read();
	for(int i=1;i<=m;i++){
		int v=read();
		q[i]={v,i};
		lsh.push_back(v);
	}
	sort(lsh.begin(),lsh.end());
	lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
	
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
		//cout<<a[i]<<" \n"[i==n];
	}
	sort(q+1,q+1+m);
	for(int i=1;i<=m;i++){
		q[i].x=lower_bound(lsh.begin(),lsh.end(),q[i].x)-lsh.begin()+1;
		//cout<<q[i].x<<"\n";
	}
	
    build(root[0],1,n+m);
    for(int i=1;i<=n;i++){
        modify(root[i],root[i-1],1,n+m,a[i] );
    }
    //query(root[x-1],root[y],1,n+m,k)
	dac(1,m,1,n);
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
}

signed main(){
    //std::ios::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);
    //freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;
	for(int i=1;i<=t;i++){
	//	cerr<<"-------------------------\n";
    //    cerr<<"test case "<<i<<"\n";
		solve();
    //    cerr<<"-------------------------\n";
	}
    return 0;
}
/*想想你要干什么？
    * 效率：15min思考，修改思路！
    * 正难则反
    * 明确数组定义
    * 可能的思路
    * 特殊情况 （ n == 1 ）？
    * 查看溢出，数组越界
    * 不要在一个方面卡死
    * 多想性质！
    while(1){
        system("data.exe > in.txt");
        system("C.exe < in.txt > std.txt");
        system("C2.exe < in.txt > baoli.txt");
		if(system("fc baoli.txt std.txt")) system("pause");
	}
7
6 1 2 3 4 7 8
9
1 2 1 2 5 5 6 3 4

6
1 2 3 2 3 2
5
5
4
2
4
5
*/