考察

手順 2. でディーラーが選ぶティーバッグのうち，フレーバー \(i\) のものの個数を \(c_i\) とおく．

難易度 \(b\) のゲームにおいて，ディーラーがあなたを敗北させるには，\(i=1,\dots,i\) で以下を満たす必要がある．

• \(c_i \leq \min(A_i, b-1)\)．
  • フレーバー \(i\) のティーバッグが \(A_i\) 個しかないので，\(A_i\) 個を超えて渡すことはできない．
  • フレーバー \(i\) のティーバッグを \(b\) 個以上渡した場合，あなたはそれらを \(b\) 個選ぶことで勝利できる．

ここから，\(x = c_1 + \dots + c_N \leq \sum_{i=1}^{N} \min(A_i, b-1)\) が必要であると分かる(ここで \(\sum_{i=1}^{N} \min(A_i, b-1)\) は，\(i=1,\dots,N\) に対する \(\min(A_i, b-1)\) の総和を表す)．

したがって，\(x > \sum_{i=1}^{N} \min(A_i, b-1)\) のときはあなたが勝利できる．

逆に，\(x = \sum_{i=1}^{N} \min(A_i, b-1)\) のときは，ディーラーが \(c_i = \min(A_i, b-1)\) を満たすように選んで渡すことができるので，あなたは敗北する．\(x < \sum_{i=1}^{N} \min(A_i, b-1)\) の場合も，その一部を選んで渡すことで同様にあなたは敗北する．

よって，勝利に必要な \(x\) の最小値は \(1 + \sum_{i=1}^{N} \min(A_i, b-1)\) である．ただし，この値が \(\sum_{i=1}^{N} A_i\) よりも大きい場合はそのような \(x\) を宣言することができないので，あなたの勝利は不可能である．

実装

毎クエリ愚直に \(1 + \sum_{i=1}^{N} \min(A_i, b-1)\) を求めていては，全体の時間計算量が \(\Theta(NQ)\) となって実行時間制限に間に合わない．そこで，この式をもう少し変形してみると，以下の \(2\) つの和に \(1\) を加えたものとして言い換えられる．

• \(A_i \leq b-1\) である \(i\) に対する \(A_i\) の総和．
• \(A_i > b\) である \(i\) の個数の \((b-1)\) 倍．

そこで，\(0 \leq y \leq \max A_i\) に対して以下の値を前もって求めておくことを考える．

• \(A_i \leq y\) である \(i\) に対する \(A_i\) の総和 \(sum[y]\)．
• \(A_i \leq y\) を満たす \(i\) の個数 \(cnt[y]\)．

このとき，求めたい値は \(1 + sum[b-1] + (N - cnt[y])(b-1)\) に等しい．

\(cnt[y], sum[y]\) を求めるには，以下の手順(このテクニックは累積和と呼ばれている)を踏めばよい．

1. すべての \(cnt[y], sum[y]\) を \(0\) で初期化する．
2. \(i=1,\dots,N\) について，\(cnt[A_i]\) に \(1\) を，\(sum[A_i]\) に \(A_i\) を加える．
3. \(y = 1, \dots, (\max A_i)\) の昇順に，\(cnt[y]\) を \(cnt[y-1] + cnt[y]\) で，\(sum[y]\) を \(sum[y-1]+sum[y]\) で更新する．

以上によって，時間計算量は前処理 \(O(N + \max A_i)\)，クエリごと \(O(1)\) となり，全体で \(O(N + \max A_i + Q)\) となって実行時間制限に間に合う．

実装例 (C++)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
using std::set;
using std::map;

typedef long long int ll;

ll n, q;
vector<ll> a;


const ll maxv = 1'000'009;

ll accum_sum[maxv + 1];
ll accum_cnt[maxv + 1];

void solve () {
	for (ll i = 0; i < n; i++) {
		accum_sum[a[i]] += a[i];
		accum_cnt[a[i]] += 1;
	}
	for (ll i = 1; i <= maxv; i++) {
		accum_sum[i] += accum_sum[i-1];
		accum_cnt[i] += accum_cnt[i-1];
	}
	// accum_sum[i] := a[0] + ... + a[i]
	// accum_cnt[i] := number of x s.t. a[x] <= i 

	for (ll qi = 0; qi < q; qi++) {
		ll b;
		cin >> b;

		ll ans = 1 + accum_sum[b-1] + (n - accum_cnt[b-1]) * (b-1);
		if (accum_cnt[b-1] == n) {
			cout << "-1" << "\n";
		} else {
			cout << ans << "\n";
		}
	}
	
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> q;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}

	solve();

	return 0;
}