Problem: While some people enjoy spending their time solving programming contests, Dina prefers taking beautiful pictures. As soon as Byteland Botanical Garden announced Summer Oenothera Exhibition she decided to test her new camera there.

The exhibition consists of l = 10^{100} Oenothera species arranged in a row and consecutively numbered with integers from 0 to l - 1. Camera lens allows to take a photo of w species on it, i.e. Dina can take a photo containing flowers with indices from x to x + w - 1 for some integer x between 0 and l - w. We will denote such photo with [x, x + w - 1].

She has taken n photos, the i-th of which (in chronological order) is [x_i, x_i + w - 1] in our notation. She decided to build a time-lapse video from these photos once she discovered that Oenothera blossoms open in the evening. 

Dina takes each photo and truncates it, leaving its segment containing exactly k flowers, then she composes a video of these photos keeping their original order and voilà, a beautiful artwork has been created!

A scene is a contiguous sequence of photos such that the set of flowers on them is the same. The change between two scenes is called a cut. For example, consider the first photo contains flowers [1, 5], the second photo contains flowers [3, 7] and the third photo contains flowers [8, 12]. If k = 3, then Dina can truncate the first and the second photo into [3, 5], and the third photo into [9, 11]. First two photos form a scene, third photo also forms a scene and the transition between these two scenes which happens between the second and the third photos is a cut. If k = 4, then each of the transitions between photos has to be a cut.

Dina wants the number of cuts to be as small as possible. Please help her! Calculate the minimum possible number of cuts for different values of k.

Input

The first line contains three positive integer n, w, q (1 ≤ n, q ≤ 100 000, 1 ≤ w ≤ 10^9) — the number of taken photos, the number of flowers on a single photo and the number of queries.

Next line contains n non-negative integers x_i (0 ≤ x_i ≤ 10^9) — the indices of the leftmost flowers on each of the photos.

Next line contains q positive integers k_i (1 ≤ k_i ≤ w) — the values of k for which you have to solve the problem.

It's guaranteed that all k_i are distinct.

Output

Print q integers — for each width of the truncated photo k_i, the minimum number of cuts that is possible.

Examples

Input

3 6 5
2 4 0
1 2 3 4 5


Output

0
0
1
1
2


Input

6 4 3
1 2 3 4 3 2
1 2 3


Output

0
1
2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
inline void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
using ll = long long;
using ld = long double;
const int MAXMEM = 200 * 1000 * 1024;
char _memory[MAXMEM];
size_t _ptr = 0;
void *operator new(size_t _x) {
  _ptr += _x;
  return _memory + _ptr - _x;
}
void operator delete(void *) noexcept {}
const string FILENAME = "input";
const int MAXN = 100228;
const int BLOCK = 35;
const int BLOCK1 = 1200;
int n, w, q;
int x[MAXN];
int ans[MAXN];
int mx[18][MAXN];
int mx1[18][MAXN];
int gr[MAXN];
inline int getmax(const int l, const int r) {
  int len = r - l + 1;
  return max(mx1[gr[len]][l], mx1[gr[len]][r - (1 << gr[len]) + 1]);
}
inline int getmin(const int l, const int r) {
  int len = r - l + 1;
  return min(mx[gr[len]][l], mx[gr[len]][r - (1 << gr[len]) + 1]);
}
inline bool check(const int l, const int r, int k) {
  if (l > r || r >= n) {
    return false;
  }
  int f = getmin(l, r);
  int f1 = getmax(l, r);
  return f + w - f1 >= k;
}
inline int findGroupEnd(const int i, const int k) {
  int l = i;
  int r = n - 1;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (check(i, mid, k)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l + 1;
}
int curs[MAXN];
int jump[MAXN];
int target[MAXN];
int val;
void calc(int i) {
  if (curs[i] == BLOCK) {
    jump[i] = 0;
    target[i] = i;
  } else {
    if (i + curs[i] >= n) {
      jump[i] = 1;
      target[i] = i + curs[i];
    } else {
      if (target[curs[i] + i] >= i + BLOCK) {
        int t = i + curs[i];
        int cnt = 1;
        while (curs[t] + t < i + BLOCK) {
          cnt++;
          t += curs[t];
        }
        target[i] = t + curs[t];
        jump[i] = cnt + 1;
      } else {
        jump[i] = 1 + jump[curs[i] + i];
        target[i] = target[curs[i] + i];
      }
    }
  }
}
void calc1(int i) {
  if (curs[i] == BLOCK) {
    jump[i] = 0;
    target[i] = i;
  } else {
    if (i + curs[i] >= n) {
      jump[i] = 1;
      target[i] = i + curs[i];
    }
  }
}
int gt[MAXN];
int ls[MAXN];
int ft[MAXN];
int ukr;
int nxt[MAXN];
bool used[MAXN];
int st[MAXN];
int uks;
int grs;
int stacker[MAXN];
int ukt = 0;
int curuk[MAXN];
int curval[MAXN];
void dfs(int start) {
  ukt = 0;
  stacker[ukt] = start;
  curuk[start] = gt[start];
  ukt++;
  uks = 0;
  curval[start] = 0;
  while (ukt) {
    int u = stacker[ukt - 1];
    if (curuk[u] == gt[u]) {
      used[u] = true;
      if (u <= grs) {
        if (target[curs[u] + u] >= u + BLOCK) {
          while (curval[u] < uks && st[curval[u]] >= u + BLOCK) {
            curval[u]++;
          }
          int l = curval[u];
          jump[u] = uks - l;
          if (curs[st[l]] == BLOCK) {
            target[u] = st[l];
          } else {
            jump[u]++;
            target[u] = st[l] + curs[st[l]];
          }
        } else {
          jump[u] = 1 + jump[curs[u] + u];
          target[u] = target[curs[u] + u];
        }
      }
      st[uks] = u;
      uks++;
    }
    if (curuk[u] == -1) {
      uks--;
      ukt--;
      continue;
    }
    int h = ft[curuk[u]];
    curuk[u] = nxt[curuk[u]];
    if (!used[h]) {
      stacker[ukt] = h;
      curval[h] = curval[u];
      curuk[h] = gt[h];
      ukt++;
    }
  }
}
void add(int a, int b) {
  if (gt[a] == -1) {
    gt[a] = ukr;
    ls[a] = ukr;
    ft[ukr] = b;
    nxt[ukr] = -1;
    ukr++;
  } else {
    nxt[ls[a]] = ukr;
    ft[ukr] = b;
    nxt[ukr] = -1;
    ls[a] = ukr;
    ukr++;
  }
}
void update(int i) {
  ukr = 0;
  for (int j = min(i + BLOCK, n); j >= max(0, i - BLOCK - 5); j--) {
    gt[j] = -1;
  }
  for (int j = min(i + BLOCK, n); j >= max(0, i - BLOCK - 5); j--) {
    used[j] = false;
  }
  for (int j = max(0, i - BLOCK - 5); j <= i; j++) {
    if (curs[j] == BLOCK || j + curs[j] >= n) {
      calc1(j);
      used[j] = true;
      continue;
    }
    add(j + curs[j], j);
  }
  grs = i;
  for (int j = min(i + BLOCK, n); j >= max(0, i - BLOCK - 5); j--) {
    if (!used[j]) {
      dfs(j);
    }
  }
}
bool bad[MAXN];
int curs2[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> w >> q;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    mx[0][i] = x[i];
    mx1[0][i] = x[i];
  }
  for (int k = 1; k <= 18; k++) {
    for (int i = 0; i < n; i++) {
      int t = min(i + (1 << (k - 1)), n - 1);
      mx[k][i] = min(mx[k - 1][i], mx[k - 1][t]);
      mx1[k][i] = max(mx1[k - 1][i], mx1[k - 1][t]);
    }
  }
  int cur = 1;
  int step = 0;
  for (int i = 1; i <= n; i++) {
    if (cur + cur <= i) {
      cur += cur;
      step++;
    }
    gr[i] = step;
  }
  vector<pair<int, int> > st;
  for (int it = 0; it < q; it++) {
    int k;
    cin >> k;
    st.push_back({k, it});
  }
  sort((st).begin(), (st).end());
  vector<pair<int, pair<int, int> > > g;
  vector<pair<int, int> > g1;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= BLOCK; j++) {
      int maxk = 0;
      if (i + j - 1 >= n) {
        maxk = 0;
      } else {
        int s = getmin(i, i + j - 1);
        int s1 = getmax(i, i + j - 1);
        maxk = max(0, s + w - s1);
      }
      g.push_back({maxk + 1, {i, j - 1}});
      if (maxk) {
        chkmax(curs[i], j);
      }
    }
    if (i + BLOCK1 <= n) {
      int s = getmin(i, i + BLOCK1 - 1);
      int s1 = getmax(i, i + BLOCK1 - 1);
      if (max(0, s + w - s1) != 0) {
        g1.push_back({max(0, s + w - s1) + 1, i});
        bad[i] = true;
      }
    }
    curs2[i] = findGroupEnd(i, 1) - i;
  }
  sort((g).begin(), (g).end());
  sort((g1).begin(), (g1).end());
  val = 1;
  int uk = 0;
  for (int i = n - 1; i >= 0; i--) {
    calc(i);
  }
  int uk1 = 0;
  for (int it = 0; it < q; it++) {
    val = st[it].first;
    while (uk < (int)(g).size() && g[uk].first <= val) {
      int gh = curs[g[uk].second.first];
      chkmin(curs[g[uk].second.first], g[uk].second.second);
      if (curs[g[uk].second.first] != gh) {
        update(g[uk].second.first);
      }
      uk++;
    }
    while (uk1 < (int)(g1).size() && g1[uk1].first <= val) {
      bad[g1[uk1].second] = false;
      curs2[g1[uk1].second] = BLOCK1 - 1;
      uk1++;
    }
    int cur = 0;
    int cnt = 0;
    while (cur < n) {
      if (curs[cur] == BLOCK) {
        if (bad[cur]) {
          cnt++;
          cur = findGroupEnd(cur, val);
        } else {
          while (!check(cur, cur + curs2[cur] - 1, val)) {
            curs2[cur]--;
          }
          cnt++;
          int val = curs2[cur];
          cur += val;
        }
      } else {
        cnt += jump[cur];
        cur = target[cur];
      }
    }
    ans[st[it].second] = cnt - 1;
  }
  for (int it = 0; it < q; it++) {
    cout << ans[it] << '\n';
  }
  return 0;
}