/*
FULL-SCORE SOLUTION OF "PASSPORT"
- The way of implementation is a bit different from official review
- It does not create graph explicitly
- It uses Dijkstra's algorithm instead of BFS, but the time complexity does not change in this implementation
- Time Complexity: O(N log N)
*/
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class state {
public:
int pos, cost;
state() : pos(-1), cost(0) {}
state(int pos_, int cost_) : pos(pos_), cost(cost_) {}
bool operator<(const state& s) const {
return cost > s.cost;
}
};
vector<int> solve(int N, int Q, const vector<int>& L, const vector<int>& R, const vector<int>& X) {
const int INF = 1012345678;
// step #1. do segment-tree-like precalculation
int sz = 1;
while (sz < N) {
sz *= 2;
}
vector<vector<int> > dat(sz * 2);
for (int i = 0; i < N; i++) {
int cl = L[i] + sz;
int cr = R[i] + sz;
while (cl != cr) {
if (cl & 1) {
dat[cl++].push_back(i);
}
if (cr & 1) {
dat[--cr].push_back(i);
}
cl >>= 1;
cr >>= 1;
}
}
// step #2. function to calculate distance
auto calc = [&](const vector<int>& initial_dist) {
vector<int> dist = initial_dist;
priority_queue<state> que;
for (int i = 0; i < N; i++) {
if (dist[i] != INF) {
que.push(state(i, dist[i]));
}
}
vector<bool> vis(N, false);
vector<bool> used(sz * 2, false);
while (!que.empty()) {
int u = que.top().pos;
que.pop();
if (!vis[u]) {
vis[u] = true;
int idx = u + sz;
while (idx >= 1 && !used[idx]) {
for (int j : dat[idx]) {
if (dist[j] > dist[u] + 1) {
dist[j] = dist[u] + 1;
que.push(state(j, dist[j]));
}
}
used[idx] = true;
idx >>= 1;
}
}
}
return dist;
};
// step #3. main part
vector<int> ini1(N, INF); ini1[0] = 0;
vector<int> ini2(N, INF); ini2[N - 1] = 0;
vector<int> d1 = calc(ini1); d1[0] = 1;
vector<int> d2 = calc(ini2); d2[N - 1] = 1;
vector<int> ini3(N);
for (int i = 0; i < N; i++) {
ini3[i] = min(d1[i] + d2[i], INF);
}
vector<int> d3 = calc(ini3);
vector<int> answer(Q);
for (int i = 0; i < Q; i++) {
answer[i] = (d3[X[i]] != INF ? d3[X[i]] - 1 : -1);
}
return answer;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
vector<int> L(N), R(N);
for (int i = 0; i < N; i++) {
cin >> L[i] >> R[i];
L[i] -= 1;
}
int Q;
cin >> Q;
vector<int> X(Q);
for (int i = 0; i < Q; i++) {
cin >> X[i];
X[i] -= 1;
}
vector<int> res = solve(N, Q, L, R, X);
for (int i = 0; i < Q; i++) {
cout << res[i] << '\n';
}
return 0;
}
