Improve algorithmic complexity
Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A[i])$ represents a point in 2D-space. Also we can think that assigning $A[j]=0$ is the same as removing the point $(j, A[j])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A[i])$.

Now the set of removed points can be represented with a set of points $(i_1, A[i_1]), (i_2, A[i_2]), \ldots, (i_k, A[i_k])$, for which $i_p &lt; i_{p+1}$ and $A[i_p] &lt; A[i_{p+1}]$ for all $1 \le p &lt; k$. A point $(j, A[j])$ is removed if there is some $p$ for which $i_p &lt; j$ and $A[i_p] &gt; A[j]$. The picture https://en.wikipedia.org/wiki/Maxima_of_a_point_set#/media/File:Maxima_of_a_point_set.svg from Wikipedia might gives intuition for this (though it is left-right mirrored compared to our definition).
This set representation can be maintained with a balanced binary search tree. We can check in $O(\log n)$ time if a point $(j, A[j])$ is removed by finding the largest $i&lt;j$ such that $(i, A[i])$ is in the set, and checking if $A[i] &gt; A[j]$. For performing the query in your problem, first check if the given point $(i, A[i])$ already is removed. If it's not, insert it into the set in $O(\log n)$ and repeatedly check if the next element with $j&gt;i$ has $A[j] &lt; A[i]$, and remove it. This can be done in $O(k \log n)$, where $k$ is the number of removed elements, so the amortized complexity if $O(\log n)$.

In summary, your queries can be answered in $O(\log n)$ amortized complexity.