Imagine that we have an array like structure A with n elements all of which are initially 0. ($A[i]=0$)
What is a data structure that supports the following operations:
1) Given an element A[i]=0 set A[i] to 1 in O(1) worst case
2) Given the index i return A[i] in O(1) worst case
3) Given the index i retrun the smallest $j\geq i$ such that $A[j]=0$ or $-1$ if there is no such index in amortized time as small as possible
Obviously an array supports the first 2. It doesnt not support 3). How to modify it?