An ordered stack S is a stack where the elements appear in increasing order, such that the top of the stack is the largest element. The stack supports the following operations: - Init(S): Create an empty ordered stack. - Pop(S): Delete and return the top element from the ordered stack - Push(S, x) : Insert x at top of the ordered stack and reestablish the increasing order by repeatedly removing the element immediately below x until x is the largest element on the stack. Example: calling Push (S,4) on the following stack will transform it as follows. - Destroy(S): Delete all elements on the ordered stack. Assume that the stack is implemented using a linked list, and that a pointer is maintained to the top element of the stack. a) What is the worst-case running time of each of the operations Init, Pop, Push, and Destroy? b) Argue that the amortized running time of all operations is O(1)