Given an array of length '$n$' with positive integers. Let's consider the sum:
$$S(p) = \sum_{i=p}^n \lfloor(\frac{a(i)}{i-p+1})\rfloor$$
where $[...]$ denotes the greatest integer function and $p = 1,2,3...n$. Now given an integer '$m$' find minimum '$p$' which satisfies $$S(p)\leq m$$ If no such '$p$' exists then output '$-1$'. The expected complexity should be $n · max(\sqrt{a(i)})$.
Any idea on how to solve it? I can find sum $S(i)$ where $i = 1$ to $n$ in $n · max(\sqrt{a(i)}$) but how to extract each $S(i)$ in $O(1)$ time? Also $n\leq 10^5$ and $a(i)\leq10^5$.