Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type Val struct {
	id, num int
}
type ByNum []Val

func (a ByNum) Len() int           { return len(a) }
func (a ByNum) Less(i, j int) bool { return a[i].num < a[j].num }
func (a ByNum) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N, M := sc.nextInt(), sc.nextInt()
	m := sc.nextIntSlice(M)
	m = append(m, N)
	Q := sc.nextInt()
	l := sc.nextIntSlice(Q)
	base := m[0] - 1
	sums := make([]int, N+1)
	for i := 1; i <= M; i++ {
		var diff int
		if i != M {
			diff = m[i] - m[i-1] - 1
		} else {
			diff = m[i] - m[i-1]
		}
		for j := 0; j < diff; j++ {
			sums[j+1] += diff - j
		}
	}
	for _, allow := range l {
		ok := N + 1
		ng := 0
		for abs(ok-ng) > 1 {
			mid := (ok + ng) / 2
			if base+sums[mid] <= allow {
				ok = mid
			} else {
				ng = mid
			}
		}
		if ok == N+1 {
			fmt.Fprintln(wtr, -1)
		} else {
			fmt.Fprintln(wtr, ok)
		}
	}

	wtr.Flush()
}

C++: //#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i, l, r) REPEAT(i,l,r,true) // [l, r)
#define rep(i, n) REP(i,0,n)           // [0, n)
#define REPEAT(i, l, r, condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n, l, r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector< int >;
using pint=pair< int, int >;

struct io {
  io() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.tie(0);
    cout << fixed << setprecision(20);
  }
} io;

template< class T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &e:v)is >> e;
  return is;
}

template< class T >
ostream &operator<<(ostream &os, vector< T > v) {
  os << "{";
  for(T &e:v)os << e << (v.size() - (int) (&e - &v[0]) > 1 ? ", " : "");
  os << "}";
  return os;
}

void _DEBUG() {}

template< typename H, typename... T >
void _DEBUG(H a, T...b) {
  cerr << a << (sizeof...(b) ? "," : "\n");
  _DEBUG(b...);
}

inline void in() {}

template< typename H, typename... T >
void in(H &a, T &... b) {
  cin >> a;
  in(b...);
}

inline void out() {}

template< typename H, typename... T >
void out(H a, T... b) {
  cout << a << (sizeof...(b) ? " " : "\n");
  out(b...);
}

template< class T >
void resz(int n, T &v) { v.resize(n); }

template< class H, class... T >
void resz(int n, H &a, T &... b) {
  a.resize(n);
  resz(n, b...);
}

template< typename V, typename H >
void resize(vector< V > &v, const H a) { v.resize(a); }

template< typename V, typename H, typename... T >
void resize(vector< V > &v, const H &a, const T... b) {
  v.resize(a);
  for(auto &v:v) resize(v, b...);
}

const int INF = 1LL << 55;
const int MOD = 1000000007;
const double EPS = 1e-8;

int N, M;
vi m;
vi cumsum_arrow(1e5 + 1);
vi cumsum_dist(1e5 + 1);
int Q;

signed main() {

  in(N, M);
  m.resize(M);
  in(m);
  m.push_back(N + 1);
  sort(begin(m), end(m));
  m.erase(unique(begin(m), end(m)), end(m));
  for(int i = 1; i < m.size(); i++) {
    int sa = m[i] - m[i - 1] - 1;
    cumsum_arrow[sa]++;
    cumsum_dist[sa] += sa;
  }

  REP(i, 1, 1e5 + 1) {
    cumsum_arrow[i] += cumsum_arrow[i - 1];
    cumsum_dist[i] += cumsum_dist[i - 1];
  }

  //showlr(cumsum_arrow, 0, 11);
  //showlr(cumsum_dist, 0, 11);
  in(Q);

  while(Q--) {
    int l;
    in(l);
    int lo = 0, hi = 1e5 + 1;

    while(hi - lo > 1) {
      int med = (hi + lo) / 2;
      // 矢の長さがmedのときのコスト
      int cost = (cumsum_dist[1e5] - cumsum_dist[med - 1]) - (cumsum_arrow[1e5] - cumsum_arrow[med - 1]) * (med - 1) + m[0] - 1;

      // show(hi, lo, cost, cost <= l);

      // costが2 lが1
      if(cost <= l) {
        hi = med;
      } else {
        lo = med;
      }
    }
    if(hi == 1e5 + 1) {
      out(-1);
      continue;
    }
    out(hi);
  }
  return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<ll,ll> P;

ll mp[111111];
ll ans[111111];

int main(){

	ll n, m;cin >> n >> m;
	vector<ll> v(m+1);
	v[m] = n+1;
	REP(i,m)cin >> v[i];

	vector<ll> seica;
	REP(i, v.size() - 1){
		if(i == 0){
			REP(j,111111)mp[j] += v[i] - 1;
		}
		int now = v[i+1] - v[i];
		for(int j = 1;j <= now;j++){
			mp[j] += now - j;
		}
	}

	//SHOW1d(mp, 20);

	int q;cin >> q;
	vector<P> que(q);
	REP(i, q){
		cin >> que[i].FI;
		que[i].SE = i;
	}

	sort(ALL(que), greater<P>());

	int nagasa = 1;
	REP(i,que.size()){
		int id = que[i].SE;
		int d = que[i].FI;
		while(nagasa < 111111 && mp[nagasa] > d)nagasa++;
		if(nagasa != 111111)ans[id] = nagasa;
		else ans[id] = -1;
	}

	REP(i,q){
		cout << ans[i] << endl;
	}
	return 0;
}