在第 $i$ 个点买一张票，就能在 $[L_i,R_i]$ 中任意行走，求从每个点出发，最少买几张票能走遍 $[1,n]$？

tag：最短路，线段树优化建图。

题目的问题是求最少代价，于是我们发现题目很像一个最短路模型：$i$ 向一个虚点 $u_i$ 连边权为 $1$ 的边，$u_i$ 向 $[L_i,R_i]$ 连代价为 $0$ 的边。连边看起来很多，但是由于连边连向的是一个区间，我们只需要线段树优化建图即可。

考虑最终的答案是什么：由于连边是连向一个区间，所以对于点 $i$，所有买的票的并，也就是我们能走到的点，构成了一个大区间。所以走遍 $[1,i]$ 的充要条件是走到 $1$。因为 $1$ 为该区间左端点。同理走遍 $[i,n]$ 的充要条件是走到 $n$，因为 $n$ 为该区间右端点。所以我们建反图并从 $1$ 与 $n$ 分别跑最短路，每一个点的答案应该是到 $1$ 的最短路加上到 $n$ 的最短路。

然后我们发现这个不对，因为到 $1$ 的最短路和到 $n$ 的最短路会有重复的路径，这一段路径只会被计算一次。例如，从点 $i$ 出发只需要买一张 $i$ 的票就可以了。

我们如果设初始 $dis_1+dis_n$ 为初始答案 $ans_u$，那么我们发现对于任意的 $(u,v,w)$，$ans_v \le ans_u + w$。于是我们考虑再次使用最短路，只不过这一次往优先队列中加入所有点作为源点进行松弛。

如果对算法进行思考，我们会发现只需要将所有票的虚点作为源点即可。原因如下：

1. 对于线段树上的点，它们只负责联通原始图中有边的点，从其出发的边权值都为 $0$，因此不用松弛。
2. 对于原有点，我们建的反图中必定有票的虚点连向原有点的边，因此只要不是无解情况，原有点必定会被松弛到。

#include<bits/stdc++.h>

using namespace std;

const int N = 4e5 + 5;

int n;
struct node {
  int u, w;
  bool operator <(const node &b) const {
    return b.w < w;
  }
};
vector<pair<int, int>> e[N << 2];
int dis[N << 2], mx[N << 2], vis[N << 2], mxn;
const int INF = 1919810;
void dij(int s) {
  for (int i = 1; i <= mxn; ++i) dis[i] = INF;
  for (int i = 1; i <= mxn; ++i) vis[i] = 0;
  priority_queue<node> q;q.push({s, 0});
  while (!q.empty()) {
    auto t = q.top();q.pop();
    int u = t.u, val = t.w;
    if (vis[u] == 1) continue;
    vis[u] = 1, dis[u] = val;
    int v, w;
    for (auto p : e[u]) {
      tie(v, w) = p;
      q.push({v, val + w});
    }
  }
  for (int i = 1; i <= mxn; ++i) {
    if (dis[i] < INF) mx[i] = mx[i] + dis[i];
    else mx[i] = INF;
  }
}
void reans() {
  priority_queue<node> q;
  for (int i = n + 1; i <= 2 * n; ++i) if (mx[i] < INF) q.push({i, mx[i]});
  for (int i = 1; i <= mxn; ++i) vis[i] = 0;
  while (!q.empty()) {
    auto t = q.top();q.pop();
    int u = t.u, val = t.w;
    if (vis[u] == 1) continue;
    vis[u] = 1, mx[u] = val;
    int v, w;
    for (auto p : e[u]) {
      tie(v, w) = p;
      q.push({v, val + w});
    }
  }
}

void add(int u, int v, int w) {
  e[v].push_back(make_pair(u, w));
}
#define ls(u) (u<<1)
#define rs(u) ((u<<1)|1)
#define mid ((l+r)>>1)
void build(int u, int l, int r) {
  if (l == r) {
    mxn = max(mxn, u + (2 * n));
    return add(u + (2 * n), l, 0);
  }
  add(u + (2 * n), ls(u) + (2 * n), 0);
  add(u + (2 * n), rs(u) + (2 * n), 0);
  build(ls(u), l, mid);
  build(rs(u), mid + 1, r);
}
void modify(int u, int l, int r, int fl, int fr, int p) {
  if (fl <= l && r <= fr) return add(p, u + (2 * n), 0);
  if (mid >= fl) modify(ls(u), l, mid, fl, fr, p);
  if (mid < fr) modify(rs(u), mid + 1, r, fl, fr, p);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> n;
  build(1, 1, n);
  for (int i = 1, l, r; i <= n; ++i) {
    cin >> l >> r;
    add(i, i + n, 1);
    modify(1, 1, n, l, r, i + n);
  }
  dij(1);
  dij(n);
  reans();
  int q;cin >> q;
  for (int i = 1, x; i <= q; ++i) {
    cin >> x;
    if (mx[x] < INF) cout << mx[x] << endl;
    else cout << -1 << endl;    
  } 

  return 0;
}