For non-Japanese, this is just a sponsored ARC.

1) sort the sequence S

2) dp[i][A] which means the answer to the original problem for the prefix 1...i of S if the start number is X=A the transition is:

dp[i][A] = dp[i-1][A%s[i]] + dp[i-1][A]*i

the first summand is when s[i] goes first; the second summand is when it doesn't go first. In the latter case, the answer remains unchanged, because doing %s[i] on number <s[i] does nothing.

Consider the operation backwards, maintain the positions that the golems would disappear, which is some prefix plus some suffix. Time complexity is $$$O(N+Q)$$$ since each upate takes $$$O(1)$$$ time.

Observations:

• If $$$i \lt j$$$ and $$$j$$$ is to fall off from left, then $$$i$$$ will also fall off from left.
• If $$$i \lt j$$$ and $$$i$$$ is to fall off from right, then $$$j$$$ will too.

So we can divide the sequence into 3 parts: $$$[1,L],[L+1,R-1],[R,N]$$$.

• The left part will fall off from left.
• The right part will fall off from right.
• The middle part will remain.

We can compute $$$L,~R$$$ using binary search.