#include<bits/stdc++.h>
#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"
using namespace std;
template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}
typedef long long ll;
typedef long double ld;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}
const int N = 1e6 + 15;
const int INF = 1e9;
int n, q;
int leaf[N];
vector<pair<int,int>> g[N];
int fake_node[N];
int maxNode;
vector<pair<int,int>> multisource;
void build(int l, int r, int id){
if(id >> 1) g[id].push_back({id >> 1, 0});// cout << id << " " << (id >> 1) << endl;
if(l == r){
leaf[l] = id;
maximize(maxNode, id);
return;
}
int mid = (l+r) >> 1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
}
void add_edge(int l, int r, int id, int u, int v, int idx){
if(r < u || l > v) return;
if(u <= l && r <= v){
//cout << id << " " << fake_node[idx] << endl;
g[id].push_back({fake_node[idx], 1});
return;
}
int mid = (l+r) >> 1;
add_edge(l,mid,id<<1,u,v,idx);
add_edge(mid+1,r,id<<1|1,u,v,idx);
}
int dist[2][N]; // 0: 1, 1: n, 2: dist(y, 1) + dist(y, n);
int d[N];
void bfs01(int turn, int source){
deque<int> dq;
for(int i = 1; i <= maxNode; i++){
d[i] = INF;
}
d[leaf[source]] = 0;
dq.push_back(leaf[source]);
while(!dq.empty()){
int u = dq.front(); dq.pop_front();
//cout << "case: " << u << endl;
for(auto [v, w] : g[u]){
//cout << v << endl;
if(minimize(d[v], d[u] + w)){
if(!w) dq.push_front(v);
else dq.push_back(v);
}
}
}
for(int i = 1; i <= n; i++) dist[turn][i] = d[fake_node[i]];
}
void dijkstra(){
for(int i = 1; i <= maxNode; i++){
d[i] = INF;
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
for(auto [u, w] : multisource){
d[u] = w;
pq.push(pii(w, u));
}
while(!pq.empty()){
int u = pq.top().se, wu = pq.top().fi;
pq.pop();
if(d[u] < wu) continue;
for(auto [v, wv] : g[u]){
if(minimize(d[v], d[u] + wv)){
pq.push(pii(d[v], v));
}
}
}
}
void solve(){
cin >> n;
build(1,n,1);
for(int i = 1; i <= n; i++){
fake_node[i] = ++maxNode;
g[fake_node[i]].push_back({leaf[i], 0});
}
for(int i = 1; i <= n; i++){
int l, r; cin >> l >> r;
add_edge(1,n,1,l,r,i);
}
bfs01(0,1);
bfs01(1,n);
for(int i = 1; i <= n; i++){
//check if i can be a source -> can go to 1 and n
// max(dist(i,1) , dist(i,n)) < INF
// merge into dist(i,1) + dist(i,n) - 1 (buy passport only one time from source)
if(max(dist[0][i], dist[1][i]) < INF){
multisource.push_back({fake_node[i], dist[0][i] + dist[1][i] - 1});
}
}
dijkstra();
cin >> q;
while(q--){
int u; cin >> u;
cout << (d[fake_node[u]] < INF ? d[fake_node[u]] : -1) << endl;
}
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
#define task "task"
if(fopen(task".INP", "r")){
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int t; t = 1; //cin >> t;
while(t--) solve();
}
/*
since L[i] <= i <= R[i] => create a segment [Li, Ri]
1 [ (i) ] n
[ (i+1)]
[(i+2) ]
[ (i-1)]
+ consider node x:
- if we can go from 1 -> x => cover all nodes from 1 -> x
- if we can go from n -> x => cover all nodes from n -> x
- an optimize path from x to 1 and n will looks like this:
x ---> y ----> 1
|
|
n
- break into 3 parts dist(x, y) + dist(y, n) + dist(y, 1)
- dist(y, n) + dist(y, 1) : use bfs01
- dist(x, y) + (dist(y, n) + dist(y, 1)): dijkstra
*/
