/** * 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); } vector<int> dijkstra(int s) { vector<int> dp(4 * n + 5, inf); priority_queue<pii> pq; dp[pos[s]] = 0; pq.push({0, pos[s]}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto [v, w] : graph[u]) if (dp[v] > dp[u] + w) { dp[v] = dp[u] + w; pq.push({-dp[v], v}); } } 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 = dijkstra(1), g = dijkstra(n); vector<int> dp(4 * n + 5, inf); priority_queue<pii> pq; 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); pq.push({-dp[u], u}); } while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto [v, w] : graph[u]) if (dp[v] > dp[u] + w) { dp[v] = dp[u] + w; pq.push({-dp[v], v}); } } 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; }