$$ public static int$[]$ copyAndInsert$($int$[]$ x$,$ int n$,$ int v$)$

$$ Complexity: O$($n$)$

$$ Preconditions:

$$ isSorted$($x$,$ n$)==$ true.

$0<$ x$.$length.

$0<$ n $<=$ x$.$length.

$$ x $!=$ null.

$$ Behavior:

$$ Return a new array y with the following properties:

$$ isSorted$($y$,$ y$.$length$)==$ true.

$$ If the first n elements of x contain v$,$ y contains only the first n elements of x$.$ Otherwise,

if the first n elements of x does not contain v$,$ then y contains the first n elements of x

and the value v$.$

$$ Postconditions:

$$ The contents of x must not be modified.

$$ Example input$/$output:

$$ Arguments: x $=[1,3,5,7],$ n $=3,$ v $=4$

$$ Return value: $[1,3,4,5]$

$$ Post$-$execution state of x: x $=[1,3,5,7]$