/** * Author: trviet * Studies at: Le Hong Phong High School for the Gifted **/ #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int maxn = 2e5 + 5, inf = 1e9; int n, q, pos[maxn], l[maxn], r[maxn]; vector<pii> graph[4 * maxn]; void Build(int id, int l, int r) { if (l == r) { pos[l] = id; return; } int mid = (l + r) >> 1; Build(id << 1, l, mid); Build(id << 1 | 1, mid + 1, r); graph[id << 1].push_back({id, 0}); graph[id << 1 | 1].push_back({id, 0}); } void Update(int id, int l, int r, int u, int v, int k, int w) { if (r < u || l > v) return; if (u <= l && r <= v) { graph[id].push_back({pos[k], w}); return; } int mid = (l + r) >> 1; Update(id << 1, l, mid, u, v, k, w); Update(id << 1 | 1, mid + 1, r, u, v, k, w); } void update_bfs01(int w, int v, deque<int> &Q) { if (w == 0) { Q.push_front(v); } else { Q.push_back(v); } } vector<int> BFSVisit(int s) { vector<int> dp(4 * n + 5, inf); deque<int> Q; dp[pos[s]] = 0; Q.push_back(pos[s]); while (!Q.empty()) { int u = Q.front(); Q.pop_front(); for (int i = 0; i < graph[u].size(); ++i) { int v = graph[u][i].first, w = graph[u][i].second; if (dp[v] > dp[u] + w) dp[v] = dp[u] + w, update_bfs01(w, v, Q); } } return dp; } void ReadData() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i]; } void Solve() { Build(1, 1, n); for (int i = 1; i <= n; ++i) Update(1, 1, n, l[i], r[i], i, 1); vector<int> f = BFSVisit(1), g = BFSVisit(n); vector<int> dp(4 * n + 5, inf); deque<int> Q; for (int i = 1; i <= n; ++i) { int u = pos[i]; if (f[u] == inf || g[u] == inf) continue; dp[u] = f[u] + g[u] - (i != 1 && i != n); Q.push_back(u); } while (!Q.empty()) { int u = Q.front(); Q.pop_front(); for (int i = 0; i < graph[u].size(); ++i) { int v = graph[u][i].first, w = graph[u][i].second; if (dp[v] > dp[u] + w) dp[v] = dp[u] + w, update_bfs01(w, v, Q); } } cin >> q; while (q-- > 0) { int x; cin >> x; cout << (dp[pos[x]] >= inf ? -1 : dp[pos[x]]) << "\n"; } } int main() { ReadData(); Solve(); return 0; }