All of the items qualify as requirements, except for the comment about 'fast' -- that's just a guideline. You need to determine what minimum performance is acceptable (ie, it can perform all of the operations you listed, and within whatever time you decide is acceptable)

O(N) isn't the greatest, but if that's your only issue, it still might be the best implementation, especially when you're dealing with small (<1000) arrays. (small being a relative thing ... which is why we need hard numbers)

You already have your main considerations for decision making -- now decide on what the acceptable times are, and/or relative scoring. For example, you might decide that it has to be able to run some given test within (x) sec -- and the test might run just the add items, or the remove items, or it might run a combination of traversal, add/removal, searching, distance determination, etc.

I'd also suggest forgetting about your derived requirement -- just consider it in terms of speed. It's possible that an implementation that requires an extra search will be faster than a bad implementation that can 'remember' the position. (and if it's a condition that doesn't happen frequently, the speed savings for not remembering might make up for the extra searches)