In the clearable list problem, we maintain a singly$-$linked list under the

following two update operations:

INSERT, which inserts an element into the list, and the newly inserted element

will become the list head;

CLEAR, which removes all the elements from the list.

It is easy to see that INSERT can be performed in O$(1)$ worst$-$case time, while CLEAR

can take O$($n$)$ time in the worst case, where n is the number of operations performed

so far starting from an initially empty list.

Your task is to show that the amortized times of performing INSERT and CLEAER are

both O$(1).$