/** * Author: trviet * Studies at: Le Hong Phong High School for the Gifted **/ #include <bits/stdc++.h> using namespace std; constexpr int N = 2e5 + 5, Log = 18; int n, q, lg2[N], l[N], r[N], x[N], y[N]; int stl[N][Log][Log], str[N][Log][Log]; int minquery(int k, int s, int t) { int j = lg2[t - s + 1]; return min(stl[s][j][k], stl[t - (1 << j) + 1][j][k]); } int maxquery(int k, int s, int t) { int j = lg2[t - s + 1]; return max(str[s][j][k], str[t - (1 << j) + 1][j][k]); } void BuildSparse(int k) { for (int i = 1; i <= n; ++i) stl[i][0][k] = x[i], str[i][0][k] = y[i]; for (int j = 1; j < Log; ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) { stl[i][j][k] = min(stl[i][j - 1][k], stl[i + (1 << (j - 1))][j - 1][k]); str[i][j][k] = max(str[i][j - 1][k], str[i + (1 << (j - 1))][j - 1][k]); } } void Init() { lg2[1] = 0; for (int i = 2; i < N; i++) lg2[i] = lg2[i / 2] + 1; } void ReadData() { cin.tie(0)->sync_with_stdio(0); Init(); cin >> n; for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i]; } int cost(int x) { int s = stl[x][0][0], t = str[x][0][0], res = 1; if (s == 1 && t == n) return res; for (int k = Log - 1; k >= 0; --k) { int i = minquery(k, s, t), j = maxquery(k, s, t); if (i > 1 || j < n) { res += (1 << k), s = i, t = j; } } int i = minquery(0, s, t), j = maxquery(0, s, t); return (i <= 1 && j >= n ? res + 1 : -1); } void Solve() { for (int i = 1; i <= n; ++i) x[i] = l[i], y[i] = r[i]; BuildSparse(0); for (int k = 1; k < Log; ++k) { for (int i = 1; i <= n; ++i) { int s = stl[i][0][k - 1], t = str[i][0][k - 1]; x[i] = minquery(k - 1, s, t), y[i] = maxquery(k - 1, s, t); } BuildSparse(k); } cin >> q; while (q-- > 0) { int st; cin >> st; cout << cost(st) << "\n"; } } int main() { ReadData(); Solve(); return 0; }