Design and implement a version of a RootishArrayStack that has only O( n) wasted space, but that can perform add(i,x) and remove(i,x) operations in O(1 + min{i, n,n i}) time. (See Section 3.3 for ideas on how to achieve this.)

Design and implement a CubishArrayStack. This three level structure implements the List interface using O(n 2/3 ) wasted space. In this structure, get(i) and set(i,x) take constant time; while add(i,x) and remove(i) take O(n 1/3 ) amortized time.