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>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  int n,m;
  cin>>n>>m;
  vector<int> p(m);
  for(int i=0;i<m;i++) cin>>p[i];
  
  vector<int> cnt(n+1,0);
  for(int i=0;i+1<m;i++) cnt[p[i+1]-p[i]-1]++;

  vector<int> v(n+2,0);
  int sum=0;
  for(int i=n;i>=1;i--){
    sum+=cnt[i];
    v[i]=v[i+1]+sum;
    //cout<<i<<":"<<v[i]<<endl;
  }
  
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int x;
    cin>>x;
    x-=p[0]-1;
    if(x<0){
      cout<<-1<<"\n";
      continue;
    }
    int l=0,r=n;
    while(l+1<r){
      int mid=(l+r)>>1;
      if(max(0,n-p[m-1]-(mid-1))+v[mid]<=x) r=mid;
      else l=mid;
    }
    cout<<r<<"\n";
  }
  cout<<flush;
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

long long n, m, q;
long long s[100005] = {0};
long long l[100005] = {0};
long long ans[100005] = {0};
long long cnt[100005] = {0};
vector<long long> dis;

void solve();

int main() {
  cin >> n >> m;
  for(long long i = 0; i < m; ++i) cin >> s[i];
  cin >> q;
  for(long long i = 0; i < q; ++i) cin >> l[i];
  solve();
  for(long long i = 0; i < q; ++i) {
    int nowans =
        lower_bound(ans + 1, ans + n + 1, l[i] - s[0] + 1,
                    greater<long long>()) -
        ans;
    if(ans[nowans] + s[0] - 1 > l[i]) nowans = -1;
    cout << nowans << endl;
  }
  return 0;
}

void solve() {
  for(int i = 1; i < m; ++i) {
    dis.push_back(s[i] - s[i - 1] - 1);
    ans[1] += dis[i - 1];
  }
  dis.push_back(n - s[m - 1]);
  ans[1] += n - s[m - 1];
  sort(dis.begin(), dis.end());
  for(int i = 1; i <= n; ++i) {
    auto it = lower_bound(dis.begin(), dis.end(), i - 1);
    cnt[i] = dis.end() - it;
  }
  for(int i = 2; i <= n; ++i) ans[i] = ans[i - 1] - cnt[i];
}

C++: //
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class reverse_range {private:struct I {int x;int operator*() {return x-1;}bool operator!=(I& lhs) {return x>lhs.x;}void operator++() {--x;}};I i, n;public:reverse_range(int n) :i({ 0 }), n({ n }){}reverse_range(int i, int n) :i({ i }), n({ n }){}I& begin() {return n;}I& end() {return i;}};
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }reverse_range operator!(){return reverse_range(*i,*n);}};
int N,M,Q;
int m[112345];
int l[112345];

int need[112345];
int pos[112345];

int main(){
    int N,M;
    cin>>N>>M;
    for(int i:range(M)){
        cin>>m[i];
        m[i]--;
    }
    cin>>Q;
    for(int i:range(Q)){
        cin>>l[i];
    }
    for(int i:range(N)){
        pos[i]=-1e7;
    }

    for(int i:range(M)){
        pos[m[i]]=m[i];
    }
    need[0]=0-pos[0]+1;
    for(int i:range(1,N)){
        pos[i]=max(pos[i],pos[i-1]);
        need[i]=i-pos[i]+1;
    }

    sort(need,need+N);
/*
    for(int i:range(N))cerr<<pos[i]<<",";
    cerr << endl;

    for(int i:range(N))cerr<<need[i]<<",";
    cerr << endl;
*/

    for(int i:range(Q)){
        const int query = l[i];
        int ok=1e6;
        int ng=0;
        if(query<m[0]){
            ok=-1;
        }
        else{
            while(abs(ok-ng)>1){
                const int mid = (ok+ng)/2;
                int sonsitu = need+N-upper_bound(need,need+N,mid);
                if(sonsitu<=query){
                    ok=mid;
                }
                else{
                    ng=mid;
                }
            }
        }
        assert(ok<=112345);
        cout<<ok<<endl;
    }



    return 0;
}