A sequence of pushs and pops is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Assume that push cost = 1, pop cost = 1, and backup cost = sizeOf(stack) when the backup is made.

Using the accounting method, show that the cost of n stack operations (including copying the stack when necessary) is O(n).

In your solution clearly explain:

(i) what your taxation scheme is,

(ii) the maximum amount of taxes that will be collected over n operations,

(iii) how your taxation scheme can pay for the cost of all the operations. Note: Your tax should be fair, not overly excessive!

Note: {Please be sure to use this values of the push cost = 1, pop cost = 1, and backup cost = sizeOf(stack)}