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>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

template<typename T>
class CumulativeSum{
public:
  int n;
  vector<T> sum;
  vector<T> A;
  int added;
  CumulativeSum():n(-1),added(0){}
  CumulativeSum(int n):n(n), sum(n+1), A(n+1),added(0){}
  CumulativeSum(const vector<T> &B):n(B.size()), sum(n+1), A(n+1),added(0){
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + B[i-1];
  }

  void apply(){
    for(int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(int i=1;i<=n;i++) A[i] = A[i] + A[i-1];
    for(int i=1;i<=n;i++) sum[i] = sum[i] + A[i-1];
    added = 0; A.clear(); A.resize(n+1);
  }

  //[l, r)にxを加算
  void add(int l, int r, T x){
    added = 1;
    assert(l <= r && 0 <= l && r <= n);
    A[l] = A[l] + x;
    A[r] = A[r] - x;
  }

  //[l, r)の和を得る
  T get(int l,int r){
    assert(l<=r && 0<=l && r<=n);
    if(added) apply();
    return sum[r] - sum[l];
  }
};


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

  int N, M;
  cin>>N>>M;
  vector<int> A(M);
  cin>>A;
  A.push_back(N+1);

  vector<Int> len;
  for(int i=0;i<(int)A.size() - 1;i++){
    len.push_back(A[i+1] - A[i]);
  }

  sort(len.begin(), len.end());
  CumulativeSum<Int> Sum(len);
  //pr(len);
  int Q;
  cin>>Q;
  while(Q--){
    int l;
    cin>>l;
    
    auto check = [&](int x){
      int idx = upper_bound(len.begin(), len.end(), x) - len.begin() ;
      int cost = Sum.get(idx, Sum.n) - x * (Sum.n - idx ) + A[0] - 1;// + (Sum.n - idx);
      //pr(l, x, idx, cost);
      return cost <= l;
    };

    int L = 0, R = N+1;
    while(L + 1 < R){
      int M = (L + R) / 2;
      // pr(M);
      check(M)? R = M:L = M;
    }
    cout<<(R==N+1?-1:R)<<endl;
  }
  
  return 0;
}

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;
}