First, this problem is equivalent to a cumulative mod over a range (that is, we take ~v \bmod a[l] \bmod a[l+1] \bmod \dots \bmod a[r]~). The second thing to notice is that if ~a[i] < v~, then ~v \bmod a[i] \le \frac v 2~ (to prove this, consider two cases: ~a[i] \le \frac v 2~ and ~a[i] > \frac v 2~).

This shows that any one shopper can buy at most ~\log_2 v~ distinct items.

We can solve this by reducing it to the subproblem: given a range ~[i, j]~ and a number ~v~, find the smallest index ~k~ where ~k < v~, or report none exists. This can be solved with a range tree.

Alternatively, we can also solve this using a heap and processing items left to right.