Consider a Lazy Sorting Data Structure, which maintains two ArrayLists: unsorted [U] and sorted [S], and implements the following public methods:

INSERT(Integer x): inserts x into U

QUERY(Integer x): Performs a binary search to see whether x is in S, and if not found, searches linearly to see whether x is in U. Returns true if x is found in either array. The data structure has a private access to a resorting method, which works as follows:

RESORT(): Removes all elements from U and appends them to S, and then mergesorts the array. Compute (with a reasonable explanation) the amortized cost of a worst-case sequence of n Lazy Data Structure public operations in these cases:

(a) All elements are stored in U so one never does a sort.

(b) RESORT is called whenever the size of U reaches 10.

(c) RESORT is called whenever the size of U reaches the size of S