Inserting values at maximal distance from current value I have the following problem.
Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules:


If all elements equal 0,set A[0] to 1
Next 1 should be set at maximal distance from any other 1s. At this
stage it will be A[size-1].
In case of equal distances, set 1 at the element with equal distance
AND with smaller index.
At any point of time, any 1 could be set back to 0 at random


Consider an example:


0000000 // initial
1000000 // just first
1000001 // second
1001001
1101001 // all given opportunities have distance 0 to any other 1, so pick up the smallest index
1111001 // again the smallest index
1110001 // we replaced a random 1 with 0
1110101 // at this step we have location with distance 1, so use it!


Input: a sequence of additions/removals of 1s.

Expected output: a sequence of accessed indices at each step.

My question is: how to compute index for a next request? Removals are trivial and it's not interesting (there is some bookkeeping, which is out of the problem's scope), but what about additions? I don't think that you can use dynamic programming or other approaches to compute next index from scratch because of randomized removals.

My idea is to maintain something similar to an interval tree, where each node correspond to 1, left subtree correspond to an interval to the left side, right subtree to right, but it lacks some important details.

Are there any already known approaches/algorithms to this problem? Or how should I proceed with my interval tree idea?
Use an interval tree to store a set of intervals, where you have one interval for each chunk of contiguous 0's.  Now to figure out where to put the next 1, you need to find the longest interval in the interval tree.  You can keep track of the longest interval in the interval tree by augmenting the data structure: store in each node the length of the longest interval under that node.  Each operation can be done in $O(\log n)$ time.