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;

int N, M;
int m[100050];
int length[100050];
int main() {
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> m[i];
    }
    m[M + 1] = N + 1;
    //length[1] = m[1] - 1;
    for(int i = 2; i <= M + 1; i++) {
        int delta = m[i] - m[i - 1];
        length[delta-1]++;
        //cout << delta << endl;
        //length[1] += 1;
        //length[delta+1] -= delta;
        //length[delta+2] += delta;
    }
    for(int i = 1; i <= N; i++) {
        //cout << i << " " << length[i] << endl;
    }
    for(int i = N-1; i >= 1; i--) {
        length[i] += length[i+1];
    }
    for(int i = 1; i <= N; i++) {
        //cout << i << " " << length[i] << endl;
    }
    for(int i = N-1; i >= 1; i--) {
        length[i] += length[i+1];
    }
    for(int i = 1; i <= N; i++) {
        //cout << i << " " << length[i] << endl;
    }
    for(int i = 1; i <= N; i++) {
        length[i] += m[1] - 1;
        //cout << i << " " << length[i] << endl;
    }
    int Q;
    cin >> Q;
    while(Q--) {
        int l;
        cin >> l;
        if(length[N] > l) {
            cout << -1 << endl;
            continue;
        }
        int ok = N;
        int ng = 0;
        while(ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if(length[mid] <= l) ok = mid;
            else ng = mid;
        }
        cout << ok << endl;
    }
    return 0;
}

C++: //実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int long long
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<ppr, Vppr ,greater<ppr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,1,1,-1,-1,0 }, dy[] = { 1,0,-1,0,1,-1,1,-1,0 };
const int SIZE1 =3e5 + 1000;
const int SIZE2 = 2010;
const int SIZE3 = 22;
const int SIZE = SIZE1;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut N, M, K, X, L, Y,H,W,Q,D;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], nums[SIZE], maps[SIZE2][SIZE2], answer = zero;
LL A[SIZE], B[SIZE];
bool nable[SIZE2][SIZE2];
LL cost[SIZE2][SIZE2];

LL solve() {
	cin >> N >> M ;
	REP(i, M) {
		LL x;
		cin >> x;
		A[x] = 1;
	}
	LL now = INF;
	EFOR(i, 1, N) {

		if (A[i] == 1) {
			now = 0;
		}
		else {
			now++;
		}
		if (now < INF) {
			B[now] += 1;

		}
	}
	VI sum(N+1);
	sum[0] = B[0];
	LL maxim = 0;
	EFOR(i, 1, N) {
		sum[i] = B[i] + sum[i-1];
		MX(maxim, sum[i]);
		//	cout << i << " " << sum[i] << endl;
	}
	cin >> Q;
	REP(i, Q) {
		LL x;
		cin >> x;
		if (maxim < N - x) {
			cout << -1 << endl;
		}else
			cout << distance(sum.begin(),lower_bound(ALL(sum),N-x))+1 << endl;
	}
	return 0;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	solve();
	//	cin >> N;
	return 0;
}

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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M;
  cin >> N >> M;

  vector<int> m(M);
  vector<int> c(100001, 0);  
  vector<int> A(100001, 0);
  vector<int> all;  
  for ( int i = 0; i < M; i++ ) {
    cin >> m[i];
    m[i]--;    
    c[m[i]]++;    
  }

  int add = 0;
  {
    int cnt = 0;
    bool f = false;    
    for ( int i = 0; i < N; i++ ) {
      if ( !f ) {
	if ( c[i] ) {
	  f = true;	  
	} else {
	  add++;
	}
      } else {
	if ( c[i] ) {
	  A[cnt]++;
	  all.push_back(cnt);	  
	  cnt = 0;	  
	} else {
	  cnt++;	  
	}
      }
    }

    if ( cnt ) all.push_back(cnt);    
  }

  int sum = 0;  
  for ( int i : all ) sum += i;
  sort(all.begin(), all.end());
  vector<int> B(N, 0);
  int idx = 0;  
  for ( int i = 0; i < N; i++ ) {
    B[i] = sum + add;    
    while ( idx < all.size() && all[idx]-i <= 0 ) idx++;    
    sum -= (all.size()-idx);    
  }

  reverse(B.begin(), B.end());

  // for ( int i : B ) cout << i << endl;
   
  int Q;
  cin >> Q;
  vector<int> l(Q);  
  for ( int i = 0; i < Q; i++ ) {
    cin >> l[i];    
    int it = upper_bound(B.begin(), B.end(), l[i]) - B.begin();
    if ( N-it+1 <= 0 || N-it+1 > N ) cout << -1 << endl;    
    else cout << N-it+1 << endl;          
  }    
  
  return 0;
}