各日の累計枚数 \(A'_i := A_1 + \dots + A_i\) を先頭から順に求めておきます。

このとき各クエリに対して、\(x \leq A'_k\) を満たす最小の \(k\) を求めればよいです(\(x > A'_N\) の場合は存在しないので \(-1\))。

\(A'_k\) は単調増加なので、答えとなる \(k_{ans}\) について以下の \(2\) つが成り立ちます。

• \(k < k_{ans}\) ならば、\(x \leq A'_k\) は満たされない。
• \(k \leq k_{ans}\) ならば、\(x \leq A'_k\) は満たされる。

この単調性より、二分探索によって \(k_{ans}\) を求めることができます。時間計算量は前処理 \(O(N)\)、クエリごとに \(O(\log N)\) です。

実装例 (C++)

#include <iostream>
#include <cstdio>
#include <vector>
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;

typedef long long int ll;

ll n, q;
vector<ll> a, x;

void solve () {
	vector<ll> accum(n+1, 0LL);
	for (ll i = 0; i < n; i++) {
		accum[i+1] = accum[i] + a[i];
	}

	for (ll i = 0; i < q; i++) {
		ll ok = n+1, ng = 0;
		while (ng + 1 < ok) {
			ll med = (ok + ng) / 2;
			if (accum[med] >= x[i]) {
				ok = med;
			} else {
				ng = med;
			}
		}

		if (ok == n+1) {
			cout << "-1" << "\n";
		} else {
			cout << ok << "\n";
		}
	}

	return;
}

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

	solve();

	return 0;
}