We want to build a stack for elements having a colour attribute $($e$.$g$.,$ blue, red, or$-$ ange, etc$).$ We say that a bunch of consecutive positions in the array for a monochro$-$ matic stretch if all the elements stored in those positions have the same colour. In addition to the usual stack operations, we want to support a maxMono$()$ operation that on a given stack returns the maximum length of any monochromatic stretch currently stored in the stack.

All operations should run in O$(1)$ time. Your data structure should take O$($n$)$ space, where n is the number of elements currently stored in the data structure.

a$)$ Design a data structure that supports the required operations in the required time and space.

b$)$ Briefly argue the correctness of your data structure and operations.

c$)$ Analyse the running time of your operations and space of your data structure.