This takes linear time in general (it's fast when `index=-1`, but not when `index=0`). Is that OK?