Insert into a Sorted List

Write a function insert that accepts a sorted list L of integers and an integer x as arguments. The function should return a sorted list with the element x inserted at the right place in the input list. The original list should not be disturbed in the process, so build and return a new list.

• The only built-in list methods you are allowed to use are append and remove. You should not use any other method provided for lists.
• Watch out for the two easy mistakes here: inserting x more than once, and not inserting x at all when it is larger than every element of L (or when L is empty).

You do not have to accept input from the user or print anything to the console. You just have to write the function definition.

Example

insert([1, 3, 7, 10, 20], 8)   ->  [1, 3, 7, 8, 10, 20]
insert([1, 3, 7, 10, 20], 22)  ->  [1, 3, 7, 10, 20, 22]

Your task

Implement this function:

def insert(L, x):

Write the function only — the arguments are read for you and the return value is printed automatically.

Arguments arrive as one Python literal per line, in this order: L, x.

Example

Input

[1, 3, 7, 10, 20]
8

Output

[1, 3, 7, 8, 10, 20]