# Brute Force: $O(N^2)$

The naive solution is easy to see, for each index, starting from the left calculate the tolerance value(the equation given) in O(N) and stop as soon as you find the value <= K

To more efficient solution

Instead of adding the contribution of elements from the right of an index, we would take elements one by one from right and add its contribution to every index on its left. Also, it is easy to see that an element contributes only indices left to it.

f(i, j) is the contribution of element i to the index j, clearly if j > i then the contribution is 0

### OBSERVATION 1

An element stop contributing to indices which are at distance greater then the element value.

### OBSERVATION 2

The sequence of contribution of an element to the left only decreases.

This comes from the fact that, as j recedes away from i, denominator in f(i, j) increases

### OBSERVATION 3

There are atmost 2*\sqrt{arr[i]} distinct value of f(i, j).

This is same as saying, \lfloor \frac{N}{i} \rfloor , as i goes from N to i, has at most 2*\sqrt{N} distinct values. For all i greater then \sqrt{N} the value of \lfloor \frac{N}{i} \rfloor will lie between [1, \sqrt{N}]. Thus there can be at most 2*\sqrt{N} distinct value.

Since there are only O(\sqrt{arr[i]}) values to fill arr[i] places and sequence only decreases, it is easy to conclude number forms a contiguous segment.

We are now in a position to do range update instead of point updates. We would be doing O(\sqrt{arr[i]}) range updates as only these many distinct elements will emanate from arr[i]

Example: Let the last element be 39, here is how its contribution to different indices would look like

. . .0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 10 10 10 10 4 4 5 6 7 9 13 19 39

Only thing left to do is to figure out the range endpoints. Which I believe one can figure out if one draws some examples on paper

For range updates use difference array as they give O(1) updation time

After seeing a increasing/decreasing sequence I was tempted to binary search the range endpoints, turned out TL is strict enough to not let that pass.

Only O(1) update and O(1) range endpoint calculation passes, i am inclined to believe

**Total time Complexity:** \mathcal{O}(N\sqrt{N})