First, sort the sequence \(a\), then consider which items will be purchased at the end.

If for an interval \([l,r]\) (with \(l \ge 2\)), all items numbered \(l \sim r\) are purchased, it means exactly \(r-l+1\) people made purchases.

Let \(f(l,r)\) denote the number of ways to completely purchase out the interval \([l,r]\). We can enumerate the last purchased item \(k\), then \(f(l,r) = \sum \limits_{l \le k \le r} f(l,k-1) \cdot f(k+1,r) \cdot (a_{r+1}-a_k)\cdot \binom{r-l}{k-l}\).

When \(l=1\), there may be ineffective purchases. We further define \(g(r,i)\) as the number of ways to completely purchase out the interval \([1,r]\) after \(i\) purchases. Again, we enumerate the last purchased item, but also add the case where nothing is purchased in the last step, \(g(r,i-1) \cdot (a_{r+1}-1) \to g(r,i)\).

Finally, perform DP from right to left. Define \(h(i,j)\) as the number of ways to purchase \(j\) items in \([i,n]\). Then consider the longest prefix purchased in the end, \(g(i,n-k) \cdot h(i,k) \cdot \binom{n}{k}\to ans_{i+k}\).

Time complexity: \(\mathcal{O}(n^3)\). Implementation(C++,5ms)