Write a procedure that, supposing that all the positions of *v*,
except maybe the last one,
are in non-decreasing order,
leaves *v* totally in non-decreasing order.

For instance, if *v* is ⟨ 2, 4, 7, 7, 8, 9, 5⟩,
it must become ⟨ 2, 4, 5, 7, 7, 8, 9⟩.

**Interface**

C++ | void insert(vector<double>& v); |

C | void insert(int n, double v[n]); |

Java | public static void insert(double[] v); |

Python | insert(u) # returns None |

insert(u: list) -> None |

**Precondition**

We have *v.size()* ≥ 1.
Moreover, the positions 0 to *v.size()*−2 of *v*
are in non-decreasing order.

**Observation**
You only need to submit the required procedure;
your main program will be ignored.

Information

- Author
- Jordi Petit
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C C++ Java Python
- User solutions
- C C++ Python