I have a [`Vector`](https://hackage.haskell.org/package/vector-0.10.12.2/docs/Data-Vector.html#t:Vector) of sorted values, for example

```
fromList [1, 2, 4, 5]

```

Now I'd like to insert another value, let's say `3` and create a new vector. In an imperative language I'd allocate an array of size 5, loop over the original vector, copy the old values, and insert the new one at the proper point, so that I obtain

```
fromList [1, 2, 3, 4, 5]

```

I can do it using *vector* API as

```
let (pre, post) = span (< x) n
in V.concat [pre, pure x, post]

```

which works, but traverses the original vector twice: Once when searching for the split and once when combining it. Is there a way how to do it in just one pass? (Another solution would be to search for the splitting point using a binary search, but I'm interested if it's possible to create a genuine single-pass solution.)