#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; template inline bool chmax(T& x, T y){ if(x < y){ x = y; return true; } return false; } template inline bool chmin(T& x, T y){ if(x > y){ x = y; return true; } return false; } constexpr int MAX = 2e+6 + 1; constexpr ll MAXK = 1e+12; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N; vector A(N); for(int i = 0; i < N; ++i) cin >> A[i]; vector> graph(N), rev(N); for(int i = 0; i < N; ++i){ int j = (i + A[i]) % N; graph[i].emplace_back(j); rev[j].emplace_back(i); } vector vs, used(N); auto dfs = [&](auto&& self, int from) -> void { used[from] = true; for(int to : graph[from]){ if(!used[to]) self(self, to); } vs.emplace_back(from); }; for(int v = 0; v < N; ++v){ if(!used[v]) dfs(dfs, v); } reverse(vs.begin(), vs.end()); int scc_num = 0; vector scc_id(N, -1); auto rdfs = [&](auto&& self, int from) -> void { scc_id[from] = scc_num; for(int to : rev[from]){ if(scc_id[to] == -1) self(self, to); } }; for(int v : vs){ if(scc_id[v] == -1){ rdfs(rdfs, v); scc_num += 1; } } vector> scc_group(scc_num); vector sum(scc_num); for(int v = 0; v < N; ++v){ scc_group[scc_id[v]].emplace_back(v); sum[scc_id[v]] += A[v]; } int u = 0; vector path_sum(1, 0); while(u != graph[u][0] && scc_group[scc_id[u]].size() == 1){ path_sum.emplace_back(path_sum.back() + A[u]); u = graph[u][0]; } vector loop_sum(1, 0); loop_sum.emplace_back(A[u]); int cur = graph[u][0]; while(cur != u){ loop_sum.emplace_back(loop_sum.back() + A[cur]); cur = graph[cur][0]; } cin >> Q; for(int i = 0; i < Q; ++i){ ll K; cin >> K; if(K < (ll)path_sum.size()){ cout << path_sum[K] << '\n'; continue; } int v = u; ll ans = path_sum.back(); K -= (ll)path_sum.size() - 1; int sz = scc_group[scc_id[v]].size(); ll loop_cnt = K / sz; ans += sum[scc_id[v]] * loop_cnt; K -= loop_cnt * sz; ans += loop_sum[K]; cout << ans << '\n'; } return 0; }